Search In The Array
You are given two arrays ‘arr’ of size ‘n’ and ‘queries’ of size ‘q’. For each element ‘q’ in the array 'queries', your task is to find the sum of all elements in the array ‘arr’ which are less than or equal to ‘q’.

For example: given array ‘arr = { 1, 2, 3, 3, 4, 5, 6, 7, 9, 10}’ and ‘ queries= { 3, 5}’

Then the sum of all elements whose value is less than or equal to

‘queries[0] = 3’ is ‘ 1+2+3+3 =9’.

‘queries[1] = 5’ is ‘1+2+3+3+4+5 =18’.

You have to return the answer of every query { 9, 18}.

Input Format :

The first line of input contains an integer ‘T’ denoting the number of test cases. The first line of each test case contains two space-separated integers ‘n’ and ‘q’, where ‘n’ denotes the number of elements in the array ‘arr’ and ‘q’ denotes the number of elements in array ‘queries’. The second line of each test case contains ‘n’ space-separated integers denoting the elements of the array ‘arr’. The third line of each test case contains ‘q’ space-separated integers denoting the elements of the array ‘queries’.

Output Format :

For every test case, return the arraylist/list/vector of size ‘q’ denoting the answer to each query. Output for each test case will be printed in a separate line.

Note :

1. You do not need to print anything; it has already been taken care of. Just implement the given function. 2. Given array ‘arr’ is sorted in ascending order.

Constraint :

1

Question

Search In The Array

You are given two arrays ‘arr’ of size ‘n’ and ‘queries’ of size ‘q’. For each element ‘q’ in the array 'queries', your task is to find the sum of all elements in the array ‘arr’ which are less than or equal to ‘q’.

For example: given array ‘arr = { 1, 2, 3, 3, 4, 5, 6, 7, 9, 10}’ and ‘ queries= { 3, 5}’

Then the sum of all elements whose value is less than or equal to

‘queries[0] = 3’ is ‘ 1+2+3+3 =9’.

‘queries[1] = 5’ is ‘1+2+3+3+4+5 =18’.

You have to return the answer of every query { 9, 18}.

Input Format :

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains two space-separated integers ‘n’ and ‘q’, where ‘n’ denotes the number of elements in the array ‘arr’ and ‘q’ denotes the number of elements in array ‘queries’.

The second line of each test case contains ‘n’ space-separated integers denoting the elements of the array ‘arr’.

The third line of each test case contains ‘q’ space-separated integers denoting the elements of the array ‘queries’.

Output Format :

For every test case, return the arraylist/list/vector of size ‘q’ denoting the answer to each query.

Output for each test case will be printed in a separate line.

Note :

1. You do not need to print anything; it has already been taken care of. Just implement the given function.
2. Given array ‘arr’ is sorted in ascending order.

Constraint :

1 <= T <= 100
1 <= N <= 1000
1 <= Q <= 1000
-10^9 <= arr[i] <= 10^9
-10^9 <= query[i] <= 10^9

Where ‘T’ represents the number of test cases, ‘N’ is the number of elements in array ‘arr’, ‘Q’ denotes the number of elements in array ‘queries’. ‘arr[i]’ represents the value of the number at ‘i’ position in ‘arr’. ‘query[i]’ represents the value of ‘i-th’ queries.

Time Limit : 1 sec

Accepted Answer

Linear search

For each query, we can iterate over the array ‘arr’ and find the required sum.

The algorithm will be-

We will use an array/list ‘answer’ to store the answer to each query.
Now, for each ‘i’ from ‘0’ to ‘q-1’:
- We will use the variable ‘sum’ to store the sum of all the elements which is less than or equal to ‘queries[i]’. Initially, ‘sum’ will be initialized to 0.
- Now for each ‘j’ from ‘0’ to ‘n-1’:
  - If ( arr[j] <= queries[i]),
    - We do, ‘sum =sum + arr[j]’
  - Else, break the loop, because the following elements will be strictly greater than queries[i].
- Insert sum in array/list ‘answer’.
We finally return the answer/list ‘answer’.

Space Complexity: O(n)Explanation:

O(Q), Where ‘Q’ is the size of a given array ‘queries’.

The space complexity due to array/list answer will be O(Q).

Time Complexity: O(n^2)Explanation:

O(N*Q), Where ‘N’ is the size of the given array/list ‘arr’ and ‘Q’ is the size of given ‘array/list‘ queries.

For each query, we are iterating over the array/list ‘arr’ in O(N) time complexity. Hence, our overall time complexity will be O(N*Q).

Python (3.5)

'''



    Time complexity: O(N*Q)

    Space complexity: O(Q)

    

    Where 'N' is length of 'arr' and 'Q' is length of 'queries'.



'''



def searchInTheArray(arr, queries, n, q):



    answer = []  # To store the answer for every query



    for i in range(q):

        ans = 0

        for j in range(n):

            if(arr[j] > queries[i]):

                break

            ans += arr[j]



        answer.append(ans)



    return answer

C++ (g++ 5.4)

/*
    Time complexity: O(N*Q)
    Space complexity: O(Q)
    
    Where 'N' is length of 'arr' and 'Q' is length of 'queries'.
*/

vector searchInTheArray(vector& arr, vector& queries, int n, int q)
{
    // To store the answer for every query
    vector answer;

    for(int i = 0; i < q; i++)
    {
        int ans = 0;
        for(int j = 0; j < n; j++)
        {
            if(arr[j] > queries[i])
            {
                break;
            }

            ans += arr[j];
        }

        answer.push_back(ans);
    }

    return answer;
}

Java (SE 1.8)

/*

    Time complexity: O(N*Q)

    Space complexity: O(Q)

    

    Where 'N' is length of 'arr' and 'Q' is length of 'queries'.

*/



import java.util.ArrayList;



public class Solution {

    public static ArrayList searchInTheArray(ArrayList arr, ArrayList queries, int n,

            int q) {



        // To store the answer for every query

        ArrayList answer = new ArrayList();



        for (int i = 0; i < q; i++) {

            int ans = 0;

            for (int j = 0; j < n; j++) {

                if (arr.get(j) > queries.get(i)) {

                    break;

                }



                ans += arr.get(j);

            }



            answer.add(ans);

        }



        return answer;



    }

}

Accepted Answer

Binary Search

The basic idea is to store the prefix sum for every index ‘i’. We will maintain a prefix sum array in which 'prefixSum[i]’ represents all elements from ‘0’ to ‘i-th’ index.

We have to find the index ‘idx’ of the last element in ‘arr’, which is less than or equal to ‘x’. We can find ‘idx’ using binary search over ‘arr’ as ‘arr’ is sorted. Then our answer will be ‘prefixSum[ idx-1]’.