Make Sum Divisible By P

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].

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.

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

Test Case 1: Output 2 is the required size of the subarray which would be removed. We cannot remove a single element to get a sum divisible by 9. The best way is to remove the subarray [5, 2], leaving us with [6, 3] with a sum of 9. Test Case 2: The output 0 is the required size of the subarray which would be removed. Here the sum of 'NUMS' elements is 6 which is already divisible by 3. Thus we do not need to remove anything.

Brute Force

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’.

Time Complexity

O(N), where ‘N’ is the number of elements in the array/list ‘NUMS’.

Since we are iterating over all the elements of the array/list ‘NUMS’ to check whether their required modulus is present in the keys of the dictionary and update the ‘RES’ with minimum sized sub-array hence, the complexity here grows by O(N).

Space Complexity

O(N), where ‘N’ is the number of elements in the array/list ‘NUMS’.

Since, here, we require an O(N) amount of space for storing the respective remainders for indexes upto ‘POSITION’ - 1 in a map ‘MAP1’, therefore, the space complexity is O(N).

Problem statement

Sample Input 1:

Sample output 1:

Explanation For Sample Input 1:

Sample Input 2:

Sample output 2:

Explanation For Sample Input 2: