Make Sum Divisible by P

Medium
1138.

Make Sum Divisible by P

Make Sum Divisible by P is a medium coding problem on arrays, hash table and prefix sum, asked in Amazon and Google interviews.

Given an array of positive integers nums and an integer p, remove the smallest contiguous subarray (possibly empty) so that the sum of the remaining elements is divisible by p. You may not remove the whole array.

Return the length of the subarray to remove, or -1 if it cannot be done.

Example 1

Input
nums = [3,2,4], p = 6
Output
1
Explanation
The total is 9; removing `[3]` leaves 6.

Example 2

Input
nums = [1,2,3], p = 7
Output
-1
Explanation
The total is 6, and no proper subarray has a sum of 6 modulo 7.

Example 3

Input
nums = [5,3,6,2], p = 4
Output
0
Explanation
The total 16 is already divisible by 4.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 1 <= p <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} p
 * @return {number}
 */
var minSubarray = function(nums, p) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Make Sum Divisible by P — Solution in Python, Java & C++

Make Sum Divisible by P solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Make Sum Divisible by P is a medium coding problem on arrays, hash table and prefix sum, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Hash Table, Prefix Sum
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an array of positive integers nums and an integer p, remove the smallest contiguous subarray (possibly empty) so that the sum of the remaining elements is divisible by p. You may not remove the whole array.

Return the length of the subarray to remove, or -1 if it cannot be done.

Example 1

Input: nums = [3,2,4], p = 6
Output: 1
Explanation: The total is 9; removing `[3]` leaves 6.

Example 2

Input: nums = [1,2,3], p = 7
Output: -1
Explanation: The total is 6, and no proper subarray has a sum of 6 modulo 7.

Example 3

Input: nums = [5,3,6,2], p = 4
Output: 0
Explanation: The total 16 is already divisible by 4.

Constraints

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

Hints for Make Sum Divisible by P

  1. Hint 1

    Let need = sum(nums) % p. You must remove a subarray whose sum is congruent to need modulo p.

  2. Hint 2

    With prefix sums mod p, a subarray (l, r] has sum need (mod p) when prefix[l] == (prefix[r] - need) mod p.

  3. Hint 3

    Sweep r from left to right, remembering the latest index at which each prefix remainder occurred; the latest one gives the shortest subarray ending at r.

How to solve Make Sum Divisible by P

Removing a subarray fixes the total exactly when the subarray's sum leaves the same remainder as the whole array — a prefix-sum-plus-hash-map search for the shortest such subarray.

Approach

  1. Compute need = total % p. If it is 0, return 0.
  2. Store last[0] = -1 (the empty prefix).
  3. For each index i, update the running prefix cur = (cur + nums[i]) % p and look up want = (cur - need + p) % p.
  4. If want was seen at index j, the subarray j+1..i works; record i - j if shorter. Then set last[cur] = i.
  5. If the best length equals n (the whole array) or nothing was found, return -1.

Why it works

The remaining sum is total - sum(sub), divisible by p iff sum(sub) ≡ need (mod p). For a subarray ending at i, that means its starting prefix remainder is want; the latest such prefix yields the shortest candidate, and overwriting last[cur] keeps exactly that.

Complexity

  • Time — O(n)
  • Space — O(min(n, p))

Pitfalls

  • The total can reach 10^14 — reduce modulo p while summing (or use 64-bit integers).
  • In languages where % keeps the sign of the dividend, add p before taking (cur - need) % p.
  • Removing the whole array is forbidden, so a best length of n means -1.

Reference solution

Python

from typing import List

def minSubarray(nums: List[int], p: int) -> int:
    need = sum(nums) % p
    if need == 0:
        return 0
    last = {0: -1}
    cur = 0
    n = len(nums)
    best = n
    for i, v in enumerate(nums):
        cur = (cur + v) % p
        want = (cur - need) % p
        if want in last:
            best = min(best, i - last[want])
        last[cur] = i
    return -1 if best == n else best

Java

public static int minSubarray(int[] nums, int p) {
    int n = nums.length;
    long need = 0;
    for (int v : nums) need = (need + v) % p;
    if (need == 0) return 0;
    Map<Long, Integer> last = new HashMap<>();
    last.put(0L, -1);
    long cur = 0;
    int best = n;
    for (int i = 0; i < n; i++) {
        cur = (cur + nums[i]) % p;
        long want = (cur - need + p) % p;
        Integer j = last.get(want);
        if (j != null) best = Math.min(best, i - j);
        last.put(cur, i);
    }
    return best == n ? -1 : best;
}

C++

int minSubarray(vector<int>& nums, int p) {
    int n = nums.size();
    long long need = 0;
    for (int v : nums) need = (need + v) % p;
    if (need == 0) return 0;
    unordered_map<long long, int> last;
    last[0] = -1;
    long long cur = 0;
    int best = n;
    for (int i = 0; i < n; i++) {
        cur = (cur + nums[i]) % p;
        long long want = (cur - need + p) % p;
        auto it = last.find(want);
        if (it != last.end()) best = min(best, i - it->second);
        last[cur] = i;
    }
    return best == n ? -1 : best;
}

JavaScript

var minSubarray = function(nums, p) {
    var n = nums.length;
    var need = 0;
    for (var i = 0; i < n; i++) need = (need + nums[i]) % p;
    if (need === 0) return 0;
    var last = new Map();
    last.set(0, -1);
    var cur = 0, best = n;
    for (var j = 0; j < n; j++) {
        cur = (cur + nums[j]) % p;
        var want = (cur - need + p) % p;
        if (last.has(want)) best = Math.min(best, j - last.get(want));
        last.set(cur, j);
    }
    return best === n ? -1 : best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets