Last Updated: 6 Feb, 2021
Search In The Array
Easy
Asked in companies
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
Approaches
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].
- If ( arr[j] <= queries[i]),
- Insert sum in array/list ‘answer’.
- We finally return the answer/list ‘answer’.
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]’.
The algorithm will be-
- We will create a prefix sum array.
- We initially initialise ‘prefixSum[0] to arr[0]’
- Now for each ‘i’ from ‘1’ to ‘n - 1’:
- ‘prefixSum[i] = prefixSum[i - 1]+ arr[i]’
- Now for each ‘i’ from ‘0’ to ‘q-1’
- We find the index of the next greatest number ‘idx’ to ‘queries[i]’ using binary search.
- We set ‘idx to binarySearch( arr, queries[q])’
- We insert ‘prefixSum[idx-1]’ in the array/list ‘answer’.
- We finally return the answer/list ‘answer’.
Similar problems