Minimum Numbers Required

Easy
0/40
Average time to solve is 15m
profile
Contributed by
45 upvotes
Asked in companies
WalmartFlipkart limited

Problem statement

You are given an array, 'ARR', consisting of ‘N’ integers. You are also given two other integers, ‘SUM’ and ‘MAXVAL’. The elements of this array follow a special property that the absolute value of each element is not more than ‘MAXVAL’.

Your task is to determine the minimum number of integers required to be added into the array such that the sum of all the elements of the array becomes equal to ‘SUM’.

Note: 
All the new numbers being added to the array must follow the original property of the array.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow. 

The first line of each test case contains a single integer ‘N’.

The second line of each test case contains two space-separated integers, ‘SUM’ and ‘MAXVAL’, denoting the required sum of the array elements, and the maximum absolute value of each element in the array.

The third and the last line of each test case contains ‘N’ space-separated integers, denoting the elements of the array, ARR.
Output Format: 
For each test case, print in a separate line a single integer, denoting the minimum number of integers required to be added into the array.

Output for each test case will be printed in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 10^6
-10^9 <= SUM <= 10^9
1 <= MAXVAL <= 10^9
-MAXVAL <= NUMS[i] <= MAXVAL

Where 'T' denotes the number of test cases, ‘N’ represents the original number of elements present in the array, ‘SUM’ represents the required sum of all the elements in the array, ‘MAXVAL’ represents the maximum absolute value of any element in the array and ARR[i] represents the value of the elements in the array.

Time Limit: 1sec
Sample Input 1:
1
3
10 4
2 -3 4
Sample Output 1:
2
Explanation for sample input 1:
In this test case, the original sum of the array elements is 3. The required sum is 10 so we need some integers that can have a sum of 7. Since we can’t have an integer more than 4, we require at least two integers. In this case, adding 4 and 3 to the array will make the sum of the array 10, and thus, we print 2.
Sample Input 2:
1
3
-10 5
2 1 4
Sample Output 2:
4
Explanation for sample input 2:
In this test case, the original sum of the array elements is 7. The required sum is -10 so we need some integers that can have a sum of -17. Since we can’t have an integer more than 5, we require at least four integers. In this case, adding -5, -5, -5, and -2 to the array will make the sum of the array -10, and thus, we print 4.
Hint

Find the sum required to be added into the array

Approaches (1)
Finding Sum of the array

 

The approach is to find the sum of all the original elements of the array. Now, we can easily find the sum required to be added into the array. So we keep adding the maximum allowed absolute value of a number that can be added into the array as long as the sum of the array does not exceed the required value of ‘SUM’. Now, we can simply add an integer equal to the difference between the value of ‘SUM’ and the current sum of all the elements in the array.

 

 

Algorithm:

 

  1. Initialize a variable, say currentSum = 0. This will be used to store the sum of the array elements.
  2. For every num in ARR, add it to currentSum.
  3. Find the absolute difference between sum and currentSum and store it as requiredSum.
  4. Define numsRequired = requiredSum / maxVal.
  5. If requiredSum % maxVal > 0, we need to increase the value of numsRequired by 1, because we need one more integer to make the sum equal to sum.
  6. Return numsRequired.
Time Complexity

O(N), where N is the number of elements in the array.


 

We are going through the entire array and finding its sum. This takes linear time. The rest of the operations take constant time.

Space Complexity

O(1)

 

We are not using any extra space

Code Solution
(100% EXP penalty)
Minimum Numbers Required
Full screen
Console