Last Updated: 11 Apr, 2021
Array Research
Moderate
Asked in company
Ninja has been interested in array ever since he was a child. At the moment he is researching a sorted array 'ARR' with the length ‘N’, containing only integers from 1 to ‘10^9’.
He wants to know how many more integers he must add to the array such that he can form any number in the range [1, ‘M’] inclusive by the sum of some elements in the array.
Note :
1. You have to return the minimum number of integers that Ninja must add.
2. The array is given in sorted order.
Can you help Ninja achieve this task?
Input Format :
The first line of input contains an integer 'T' representing the number of test cases.
The first line of each test case contains two single space-separated integers ‘N’ and ‘M’ denoting the number of elements in the array and upper bound of the sum range respectively.
The second line of each test case contains 'N' space-separated integers.
Output Format :
For each test case, return a single integer denoting the minimum number of integers added in the array.
The output for each test case is printed in a separate line.
Constraints :
1 <= T <= 5
1 <= N <= 5000
1 <= M <= 10 ^ 9
1 <= ARR[i] <= 10 ^ 9
Where ‘ARR[i]’ denotes the element of the array at index i.
Time limit: 1 sec
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function.
Approaches
The idea here is to first find the smallest number that is not possible to form using sum of elements and then add that in the array.
Let's suppose that we can form all numbers from [1, ‘MISS’ - 1] using elements till ‘i’th index.
But we cant form ‘MISS’ and ‘i+1’th element is greater than ‘MISS’ so we need to add
‘MISS’ in the array to form it.
Now, we can able to make all sum from [1, 2 * ‘MISS’ - 1] and if ‘i+1’th element is still greater then we repeat the process else we add ‘i+1’th index in the range and continue the process.
For example: let suppose ‘ARR’ = [1,2,4,10] and ‘M’ = 20
Using the numbers 1, 2 and 4, we can form all sums from 0 to 7, but we can't form 8 and as the next element is 10 i.e. greater than 8 so it also does not help in forming 8 so we definitely need to add 8 in the array.
Now, we can form sum from 0 to 15 as now 10 is smaller than 15 we add 10 to the range and we can form sum from 0 to 25 which complete our range and we got the solution i.e. 1.
Algorithm:
- Declare two variables ‘ANS’ := 0 and ‘MISS’ := 0
- Traverse the array ‘ARR’ using ‘i’ ranges from 0 to ARR.size
- Repeat the steps till ARR[i] > MISS + 1 and MISS < m
- ANS = ANS + 1
- MISS = 2 * MISS + 1
- MISS = MISS + ARR[i]
- Repeat the steps till ARR[i] > MISS + 1 and MISS < m
- Repeat the steps till M > MISS + 1
- ANS++
- MISS = 2 * MISS + 1
- return ANS