Last Updated: 17 Apr, 2021
Make Sum Divisible By P
Moderate
Asked in companies
You are given an array/list of positive integers ‘NUMS’ of size 'N' and positive integer 'P'. You need to remove the smallest subarray (possibly empty) such that the sum of the remaining elements is divisible by ‘P’.
Your task is to print the length of the smallest subarray that you need to remove, or -1 if it's impossible.
Note:
1. It is not allowed to remove the whole array.
2. A subarray is defined as a contiguous block of elements in the array.
Example:
Suppose given ‘NUMS’ is [3, 1, 4, 2] and ‘P’ is 6.
The sum of the elements in ‘NUMS’ is 10, which is not divisible by 6. We can remove the subarray [4], and the sum of the remaining elements is 6, which is divisible by 6.
So print ‘1’ as a length of the removed subarray [4].
Input Format
The first line of input contains a single integer ‘T’ denoting the number of test cases given. Then next ‘T’ lines follow:
The first line of each test case input contains two single space-separated integers, where the first integer 'N' represents the number of the elements in the ‘NUMS’ array/list and the second integer is the value of ‘P’.
The next line of each test case contains ‘N’ space-separated integers denoting the elements of the ‘NUMS’ array/list.
Output Format:
For every test case, print the length of the smallest subarray (array/list) that you need to remove, or -1 if it's impossible.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraint :
1 <= T <= 100
1 <= NUMS.length <= 5 * 10^3
1 <= NUMS[i] <= 10^9
1 <= P <= 10^9
Where T denotes the number of test cases, N denotes the number of elements present in the ‘NUMS’ array with ‘P’ being the number that is used to divide the numbers in the ‘NUMS’ array.
Time Limit: 1sec
Approaches
Approach: The problem provides us with ‘NUMS’ (an array of numbers) and a value ‘P’ and wants us to find a subarray with the smallest length so that the sum of other elements can be divided by ‘P’.
Assuming that the sum of nums is ‘S’, the sum of the target subarray is ‘S1’, and the sum of other elements in the nums is ‘S2’. Then, ((‘S’ – ‘S1’) % P + ‘S2’ % P) must be equal to ‘S’ % P.
But, (‘S’ – ‘S1’) % P == 0 should be true.
Therefore, ‘S’ % P == ‘S1’ % P, so both subarray sum and the total sum should leave the same remainder when divided by P. Hence, the task is to find the length of the smallest subarray whose sum of elements will leave a remainder of (‘S’ % P).
The algorithm to calculate the required will be:
- Initialize a variable ‘RES’ as INT_MAX to store the minimum length of the subarray to be removed.
- Calculate the total sum ‘TOTAL_SUM’ and the remainder which it leaves when divided by ‘P’, which is then stored in the ‘TARGET_REMAINDER’ variable.
- Create a variable ‘TOTAL_SUM’ to store the remainder of each ‘ARR[i]’ when it is divided by ‘P’.
- Now, traverse the given ‘NUMS’ array and maintain a map in ‘MAP1’ to store the recent positions of the remainder encountered and keep track of the minimum required subarray having the remainder same as the target remainder ‘TARGET_REMAINDER’.
- Check If there exists any key in the map which is equal to the difference of the current remainder with the target remainder modulo ‘P’.
- (‘CURR_REMAINDER’ – ‘TARGET_REMAINDER’ + ‘P’) % ‘P’, then store that subarray length in variable ‘RES’ as the minimum of ‘RES’ and current length found.
- Finally, if ‘RES’ is unchanged then return “-1”. Otherwise, return the value of ‘RES’.
Approach: The problem provides us ‘NUMS’ (an array of numbers) and a value ‘P’ and wants us to find a subarray with the smallest length so that the sum of other elements can be divided by ‘P’.
Assuming that the sum of nums is ‘S’, the sum of the target subarray is ‘S1’, and the sum of other elements in the nums is ‘S2’. Then, we will have ‘S’ = ‘S1’ + ‘S2’.
Now we know that ‘S2’ % ‘P’ == 0, we take modular ‘P’ for equation ‘S’ = ‘S1’ + ‘S2’, then we have ‘S’ % ‘P’= ‘S1’ % ‘P’. As ‘S’ is a known number i.e., sum(‘NUMS’), we here use the variable ‘TARGET’ to denote ‘S’ % ‘P’.
After that, the problem becomes finding a subarray with the smallest length and satisfying the equation ‘S1’ % ‘P’ == ‘TARGET’, where ‘S1’ is the sum of a subarray.
The algorithm to calculate the required will be:
- Initialize a ‘TARGET’ variable with the sum(‘NUMS’) mod ‘P’. Return 0 if ‘TARGET’ is 0.
- To solve this problem, the trick here is to store the remainder of the prefix sum, instead of the prefix sum itself. In particular, we use a dictionary/map ‘PREFIX_REMAINDER’ to map the remainder of an element's prefix sum to its ‘POSITION’ - 1. Hence we initialise ‘PREFIX_REMAINDER’ = {0: -1}.
- While we scan the array, we calculate (‘REMAINDER’ - ‘TARGET’) % ‘P’, and check if it is already in the ‘PREFIX_REMAINDER’. If so, then we found a subarray that satisfies the requirement. We determine if the length of the subarray ‘I’ - ‘PREFIX_REMAINDER’[(‘REMAINDER’ - ‘TARGET’) % ‘P’] is smaller than the current smallest length, and update the length accordingly.
- Finally, we add/update the position for the remainder. We update the position because the older position will always give us a longer subarray comparing to the current position. We return the required minimum length of the subarray which would be removed else we return -1 if there is no such subarray possible.