Ask Question
30 July, 13:05

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.

+4
Answers (1)
  1. 30 July, 13:35
    0
    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)
Know the Answer?
Not Sure About the Answer?
Find an answer to your question 👍 “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 ...” in 📗 Mathematics if the answers seem to be not correct or there’s no answer. Try a smart search to find answers to similar questions.
Search for Other Answers