Array Research

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
1 upvote
Asked in company
Uber

Problem statement

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?

Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1 :
2
3 10
1 3 5
4 15
1 2 7 10
Sample Output 1 :
1
1
Explanation of Sample Output 1 :
Test Case 1 : 
Possible sums that can be formed are 1, 3, 4, 5, 6, 8, 9.
To form 2,7,10, we need to add “2” in the array.
Therefore, only 1 integer is required to form all the sums in the range [1, 10]. 

Test Case 2 : 
We need to only add 4 and we will be able to form all sums in the range [1,15]
Therefore, the minimum number required is 1.
Sample Input 2 :
3
5 20
1 3 7 9 10
4 18 
2 4 8 16
4 30
3 4 5 6
Sample Output 2 :
1
1
3
Hint

Try to find the minimum number that can’t form.

Approaches (1)
Brute Force

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 M > MISS + 1
    • ANS++
    • MISS = 2 * MISS + 1
  • return ANS
Time Complexity

O( N + log(M) ), where ‘N’ is the size of the array and ‘M’ is the upper bound of the range.

 

In the worst case, if all elements are 1 then we iterate all elements of the array, and then to complete the range we need O(log(M)) (due to the second loop which multiply by 2 on each iteration till equals ‘M’ ) more operations as MISS.

Space Complexity

O(1).

 

We are not storing anything so space complexity is O(1).

Code Solution
(100% EXP penalty)
Array Research
Full screen
Console