Search In The Array

Easy
0/40
Average time to solve is 15m
profile
Contributed by
40 upvotes
Asked in companies
Goldman SachsHCL TechnologiesOYO

Problem statement

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}.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
5 2
1 2 3 4 5
2 4  
6 3
2 3 3 4 6 7
3 6 7
Sample Output 1 :
3 10
8 18 25
Explanation of sample input 1 :
Test Case 1 :

Given array ‘arr = { 1, 2, 3, 4, 5}’
Query 1. ‘queries[0] = 2’ sum of all the elements which are less than or equal to ‘2’ is ‘ 1+2 =3’.
Query 2. ‘queries[1] = 4’ sum of all the elements which are less than or equal to ‘4’ is ‘ 1+2 +3 +4=10’.

Hence return { 3, 10}


Test Case 2 :

Given array ‘arr = { 2, 3, 3, 4, 6, 7}’
Query 1. ‘queries[0] = 3’ sum of all the elements which is less than or equal to ‘3’ is ‘ 2+3+3 =8’.
Query 2. ‘queries[1] = 6’ sum of all the elements which is less than or equal to ‘6’ is ‘ 2 +3+3+4+6=18’.
Query 3. ‘queries[2] = 7’ sum of all the elements which is less than or equal to ‘7’ is ‘ 2 +3+3+4+6+7=25’

Hence return { 8, 18, 25}
Sample Input 2 :
2
9 2
1 2 3 4 5 6 7 8 9
4 10
5 3
2 3 4 5 5 
1 2 5
Sample Output 2 :
10 45
0 2 19
Hint

Search the element in the array.

Approaches (2)
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’.
Time Complexity

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).

Space Complexity

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

 

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

Code Solution
(100% EXP penalty)
Search In The Array
Full screen
Console