Let A and B be two sequences of n integers each, in the range [1, n4]. Given an integer x, describe an O (n) - time algorithm for determining if there is an integer a in A and an integer b in B such that x = a + b.

In the question above we are given two sequence of numbers A and B, we also given an integer x.

The O (n) - time algorithm to determine if there is an integer a is described below:

/ / Create a space in the memory for size of the sequence

Declare A[], B[], x, n

Declare String z1[], z2[]

/ / Read in two sequences as z1 and z2 and also read in the size of the sequence

input n

input z1

input z2

//carry out Tokenization on string z1 and z2 and then convert it into / /integers

StringTokenizer A1 = new stringTokenizer (z1)

StringTokenizer A2 = new stringTokenizer (z2)

//Start a for loop to store the values of the sequence A1 into the integer

//array A and B

For i = 1 to n

//Convert the tokens in the string tokenizer into

/ / integer and store them into the array A and B.

A[i] = integer. parseint (A1. nextToken ())

B[i] = integer. parseint (A2. nextToken ())

End

//Input the value of the integer x.

Input x

//If the function checkSum () returns true, then there

//exists two integers a and b in the two arrays A and B

//such that x = a + b. Pass the arrays A, B, and integer x

//to the function checkSum ().

if (checksum (A, B, x))

Display "There exists x = a + b."

else

Display "There does not exist x = a + b."

//Define the function checksum ().

boolean checksum (int[] A, int[] B, int x)

//Create a hash set of integers.

HashSet hset = new HashSet ()

//Start the for loop till the length of the integer

//array A.

for i = 1 to A. length

//Add the items of the integer array A to the

//hash set of integers.

hset. add (A[i])

end

//Start the for loop till the length of the integer

//array A.

for i = 1 to A. length

//If the hash set contains a number equal to x -

//B[i], then return true.

if (hset. contains (x - B[i])

return true

end

end

return false

end

Step-by-step explanation:

We created this hash set of integers in order to add elements of A in O (n) time

We subtracted each value of B from the x value and then we carried out a check to know whether the resultant value is present in the hash set of integers

Now if the value is present in the hash set, this then means that there exists two integers a and b in the array A and B such that x = a + b

Note that the time complexity of this algorithm is O (n)