Scale Engineer

Make Sum Divisible by P

Med
#1462Time: O(N^2), where N is the number of elements in `nums`. The nested loops result in a quadratic number of operations as we consider every possible subarray.Space: O(1), as we only use a few variables to store the sums and the minimum length, regardless of the input size.2 companies
Patterns
Prefix Sum
Data structures
ArrayHash Table
Companies
SamsungPhonePe

Prompt

Given an array of positive integers nums, remove the smallest subarray (possibly empty) such that the sum of the remaining elements is divisible by p. It is not allowed to remove the whole array.

Return the length of the smallest subarray that you need to remove, or -1 if it's impossible.

A subarray is defined as a contiguous block of elements in the array.

 

Example 1:

Input: nums = [3,1,4,2], p = 6
Output: 1
Explanation: 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.

Example 2:

Input: nums = [6,3,5,2], p = 9
Output: 2
Explanation: 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 sum 9.

Example 3:

Input: nums = [1,2,3], p = 3
Output: 0
Explanation: Here the sum is 6. which is already divisible by 3. Thus we do not need to remove anything.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • 1 <= p <= 109

Approaches

2 approaches with complexity analysis and trade-offs.

This approach systematically checks every possible contiguous subarray within the given array nums. For each subarray, it calculates its sum and checks if this sum's remainder when divided by p is the one we need to make the total sum divisible by p. To avoid a cubic time complexity, the sum of the subarray is calculated incrementally in the inner loop.

Algorithm

  1. Calculate the total sum of all elements in nums. Let's call it totalSum.
  2. Determine the required remainder of the subarray to be removed. This is target_rem = totalSum % p.
  3. If target_rem is 0, the array sum is already divisible by p. No removal is needed, so return 0.
  4. Initialize a variable minLength to n (the length of the array), which will store the length of the smallest valid subarray found.
  5. Use nested loops to iterate through all possible subarrays. The outer loop i runs from 0 to n-1 (start index), and the inner loop j runs from i to n-1 (end index).
  6. For each starting index i, maintain a currentSum for the subarray starting at i. As j increments, add nums[j] to currentSum.
  7. In the inner loop, check if currentSum % p == target_rem.
  8. If the condition is met, it means removing the subarray nums[i...j] would make the remaining sum divisible by p. Update minLength = min(minLength, j - i + 1).
  9. After the loops complete, if minLength is still n, it means no suitable subarray was found (or the only one was the entire array, which is not allowed). In this case, return -1. Otherwise, return minLength.

Walkthrough

First, we need to figure out what property the sum of the removed subarray must have. Let the total sum of nums be S and the sum of the subarray to be removed be S_sub. We want the sum of the remaining elements, S - S_sub, to be divisible by p. In terms of modular arithmetic, this means (S - S_sub) % p == 0, which simplifies to S % p == S_sub % p.

So, the problem reduces to finding the shortest subarray whose sum modulo p is equal to the total sum modulo p. Let's call this required remainder target_rem. If target_rem is already 0, we don't need to remove anything, and the answer is 0.

Otherwise, we can iterate through all possible starting positions i and ending positions j of a subarray. For each subarray, we compute its sum and check if its remainder modulo p equals target_rem. We keep track of the minimum length of such a subarray found so far. If, after checking all subarrays, the minimum length found is still the length of the entire array, it's impossible to solve by removing a proper subarray, so we return -1.

class Solution {    public int minSubarray(int[] nums, int p) {        long totalSum = 0;        for (int num : nums) {            totalSum += num;        }         int targetRem = (int)(totalSum % p);        if (targetRem == 0) {            return 0;        }         int n = nums.length;        int minLength = n;         for (int i = 0; i < n; i++) {            long currentSum = 0;            for (int j = i; j < n; j++) {                currentSum += nums[j];                if (currentSum % p == targetRem) {                    minLength = Math.min(minLength, j - i + 1);                }            }        }         return minLength == n ? -1 : minLength;    }}

Complexity

Time

O(N^2), where N is the number of elements in `nums`. The nested loops result in a quadratic number of operations as we consider every possible subarray.

Space

O(1), as we only use a few variables to store the sums and the minimum length, regardless of the input size.

Trade-offs

Pros

  • Simple to understand and implement.

  • Uses constant extra space.

Cons

  • The O(N^2) time complexity is too slow for the given constraints (N up to 10^5) and will result in a 'Time Limit Exceeded' error on most platforms.

Solutions

class Solution {public  int minSubarray(int[] nums, int p) {    int k = 0;    for (int x : nums) {      k = (k + x) % p;    }    if (k == 0) {      return 0;    }    Map<Integer, Integer> last = new HashMap<>();    last.put(0, -1);    int n = nums.length;    int ans = n;    int cur = 0;    for (int i = 0; i < n; ++i) {      cur = (cur + nums[i]) % p;      int target = (cur - k + p) % p;      if (last.containsKey(target)) {        ans = Math.min(ans, i - last.get(target));      }      last.put(cur, i);    }    return ans == n ? -1 : ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem