Make Sum Divisible by P

Medium Arrays & Hashing Prefix Sum Strategy Original on LeetCode

Reported atPhonePeRazorpay

Make Sum Divisible by P is a medium arrays & hashing problem solved with the prefix sum strategy pattern. The best approach, optimal (prefix remainders + hash map), runs in O(n) time and O(min(n, p)) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (every subarray) up.

Problem

You are given an array of positive integers nums and an integer p. Remove the shortest contiguous subarray (possibly empty) so that the sum of the remaining elements is divisible by p. You are not allowed to remove the entire array.

Return the length of that shortest subarray, or -1 if no allowed removal makes the remaining sum divisible by p.

Examples

Example 1

Input
nums = [4, 7, 2, 6], p = 5
Output
1
Why
The total is 19, which leaves remainder 4. Removing [4] leaves 15, a multiple of 5.

Example 2

Input
nums = [5, 10], p = 5
Output
0
Why
The total 15 is already divisible by 5, so nothing has to be removed.

Example 3

Input
nums = [2, 3], p = 7
Output
-1
Why
The only subarray with the right remainder is the whole array, which may not be removed.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 1 <= p <= 10^9

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (every subarray)O(n²)O(1)
Optimal (prefix remainders + hash map)O(n)O(min(n, p))

1Brute force (every subarray)

TimeO(n²)Every (start, end) pair is visited once.
SpaceO(1)Only a few counters.

Compute need = total % p. Try every start index and grow the subarray to the right, keeping its sum modulo p. Whenever the remainder equals need and the subarray is not the whole array, it is a candidate.

  1. need = total % p; if need == 0 return 0.
  2. For each i, set cur = 0 and for j from i: cur = (cur + nums[j]) % p.
  3. If cur == need and j - i + 1 < n, update the best length.
  4. Return best, or -1 if nothing was found.
class Solution {
    public int minSubarray(int[] nums, int p) {
        int n = nums.length;
        long total = 0;
        for (int x : nums) total += x;
        long need = total % p;
        if (need == 0) return 0;
        int best = n;
        for (int i = 0; i < n; i++) {
            long cur = 0;
            for (int j = i; j < n; j++) {
                cur = (cur + nums[j]) % p;
                if (cur == need && j - i + 1 < best) best = j - i + 1;
            }
        }
        return best < n ? best : -1;
    }
}

2Optimal (prefix remainders + hash map)

TimeO(n)One pass with O(1) hash map work per element.
SpaceO(min(n, p))At most one map entry per distinct prefix remainder.

If the prefix remainder at the right end is cur, the subarray ending here has remainder need exactly when the prefix just before its start had remainder (cur - need) mod p. Store the latest index of each prefix remainder; the latest one gives the shortest subarray ending at the current index.

  1. need = total % p; if need == 0 return 0.
  2. last = {0: -1}; cur = 0; best = n.
  3. For each i: cur = (cur + nums[i]) % p; want = (cur - need + p) % p; if want is in last, best = min(best, i - last[want]).
  4. Record last[cur] = i.
  5. Return best < n ? best : -1 (removing everything is not allowed).
class Solution {
    public int minSubarray(int[] nums, int p) {
        int n = nums.length;
        long total = 0;
        for (int x : nums) total += x;
        int need = (int) (total % p);
        if (need == 0) return 0;
        Map<Integer, Integer> last = new HashMap<>();
        last.put(0, -1);
        long cur = 0;
        int best = n;
        for (int i = 0; i < n; i++) {
            cur = (cur + nums[i]) % p;
            int want = (int) ((cur - need + p) % p);
            Integer at = last.get(want);
            if (at != null) best = Math.min(best, i - at);
            last.put((int) cur, i);
        }
        return best < n ? best : -1;
    }
}

Edge cases to test

  • The total is already divisible by p (answer 0)
  • Only the whole array would work (answer -1)
  • p = 1: every sum is divisible
  • Large values: running sums overflow a 32-bit integer
  • p larger than the total sum

Hints

Hint 1

Let need = total % p. You must remove a subarray whose sum leaves remainder need when divided by p.

Hint 2

A subarray sum is a difference of two prefix sums. Write the condition with prefix remainders: (pre[j] - pre[i]) % p == need.

Hint 3

For each right end, which prefix remainder do you need on the left? Keep the latest index of every prefix remainder in a hash map.

FAQ

What is the best time complexity for Make Sum Divisible by P?

Optimal (prefix remainders + hash map) runs in O(n) time and O(min(n, p)) extra space. One pass with O(1) hash map work per element.

Which pattern does Make Sum Divisible by P use?

It is a arrays & hashing problem that uses the prefix sum strategy pattern. Other problems with the same pattern: Subarray Sum Equals K, Subarray with given XOR, Range Sum Query - Immutable.

Is there a brute force solution for Make Sum Divisible by P?

Yes. Brute force (every subarray) takes O(n²) time and O(1) space. Compute need = total % p.

Which edge cases should I test for Make Sum Divisible by P?

The total is already divisible by p (answer 0); Only the whole array would work (answer -1); p = 1: every sum is divisible; Large values: running sums overflow a 32-bit integer; p larger than the total sum.