Answer:
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<Integer> 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
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)