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

Array Hash Table

Companies

Samsung PhonePe

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 <= 10⁵
1 <= nums[i] <= 10⁹
1 <= p <= 10⁹

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

Calculate the total sum of all elements in nums. Let's call it totalSum.
Determine the required remainder of the subarray to be removed. This is target_rem = totalSum % p.
If target_rem is 0, the array sum is already divisible by p. No removal is needed, so return 0.
Initialize a variable minLength to n (the length of the array), which will store the length of the smallest valid subarray found.
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).
For each starting index i, maintain a currentSum for the subarray starting at i. As j increments, add nums[j] to currentSum.
In the inner loop, check if currentSum % p == target_rem.
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).
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.

1class Solution {2    public int minSubarray(int[] nums, int p) {3        long totalSum = 0;4        for (int num : nums) {5            totalSum += num;6        }7 8        int targetRem = (int)(totalSum % p);9        if (targetRem == 0) {10            return 0;11        }12 13        int n = nums.length;14        int minLength = n;15 16        for (int i = 0; i < n; i++) {17            long currentSum = 0;18            for (int j = i; j < n; j++) {19                currentSum += nums[j];20                if (currentSum % p == targetRem) {21                    minLength = Math.min(minLength, j - i + 1);22                }23            }24        }25 26        return minLength == n ? -1 : minLength;27    }28}

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.

This optimal approach leverages prefix sums and a hash map to solve the problem in linear time. The core idea is that the sum of a subarray nums[i..j] can be expressed as the difference between two prefix sums. By using modular arithmetic, we can transform the problem into finding two prefix sums with a specific relationship between their remainders.

Algorithm

Calculate totalSum of nums and find the remainder target_rem = totalSum % p.
If target_rem == 0, return 0.
Initialize a HashMap<Integer, Integer> called remainderMap to store (remainder, last_index) pairs. Add a base case remainderMap.put(0, -1) to handle subarrays that start from index 0.
Initialize minLength = n and currentSum = 0.
Iterate through the array with index j from 0 to n-1: a. Add nums[j] to currentSum. b. Calculate the current prefix sum remainder: current_rem = currentSum % p. c. We need to find a previous prefix sum whose remainder prev_rem satisfies (current_rem - prev_rem) % p == target_rem. This means we are looking for needed_rem = (current_rem - target_rem + p) % p. d. Check if remainderMap contains needed_rem. If it does, it means a subarray ending at j with the desired sum exists. The start of this subarray is remainderMap.get(needed_rem) + 1. Calculate its length j - remainderMap.get(needed_rem) and update minLength. e. Store the current prefix sum's remainder and its index: remainderMap.put(current_rem, j).
After the loop, if minLength remains n or is not updated, it's impossible. Return -1. Otherwise, return minLength.

Walkthrough

The problem asks for the shortest subarray nums[i..j] such that sum(nums[i..j]) % p == target_rem, where target_rem = sum(nums) % p.

Let prefixSum[k] be the sum of elements from nums[0] to nums[k]. Then sum(nums[i..j]) = prefixSum[j] - prefixSum[i-1]. The condition becomes (prefixSum[j] - prefixSum[i-1]) % p == target_rem.

Let's work with remainders. Let rem_j = prefixSum[j] % p and rem_i_minus_1 = prefixSum[i-1] % p. The equation is (rem_j - rem_i_minus_1 + p) % p == target_rem. We can rearrange this to find the remainder we're looking for: rem_i_minus_1 = (rem_j - target_rem + p) % p.

This means that as we iterate through the array and calculate the prefix sum remainder rem_j at each index j, we can look for a previously seen prefix sum remainder rem_i_minus_1 that satisfies the condition. A hash map is perfect for this: we can store the remainders of prefix sums we've seen so far and the latest index at which they occurred.

We iterate through the array, maintaining the current prefix sum. At each index j, we calculate the current_rem. Then we calculate the needed_rem as shown above. We query the hash map for this needed_rem. If found at index i-1, we have a candidate subarray from i to j, and we update our minimum length. We then store the current_rem and its index j in the map for future lookups.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public int minSubarray(int[] nums, int p) {6        int n = nums.length;7        long totalSum = 0;8        for (int num : nums) {9            totalSum += num;10        }11 12        int targetRem = (int)(totalSum % p);13        if (targetRem == 0) {14            return 0;15        }16 17        Map<Integer, Integer> remainderMap = new HashMap<>();18        remainderMap.put(0, -1); // Base case for subarrays starting at index 019        int minLength = n;20        long currentSum = 0;21 22        for (int j = 0; j < n; j++) {23            currentSum += nums[j];24            int currentRem = (int)(currentSum % p);25            26            int neededRem = (currentRem - targetRem + p) % p;27            28            if (remainderMap.containsKey(neededRem)) {29                int prevIndex = remainderMap.get(neededRem);30                minLength = Math.min(minLength, j - prevIndex);31            }32            33            remainderMap.put(currentRem, j);34        }35 36        return minLength == n ? -1 : minLength;37    }38}

Complexity

Time

O(N), where N is the length of `nums`. We iterate through the array a constant number of times, and hash map operations take O(1) on average.

Space

O(min(N, P)). The hash map can store at most `P` distinct remainders. If `N < P`, it will store at most `N+1` key-value pairs.

Trade-offs

Pros

Highly efficient with a linear time complexity, making it suitable for large inputs.
Solves the problem in a single pass after an initial pass to calculate the total sum.

Cons

Requires extra space for the hash map, which can be up to O(min(N, P)).
The logic is more complex than the brute-force approach.

Solutions

Solution

1class Solution {2public3  int minSubarray(int[] nums, int p) {4    int k = 0;5    for (int x : nums) {6      k = (k + x) % p;7    }8    if (k == 0) {9      return 0;10    }11    Map<Integer, Integer> last = new HashMap<>();12    last.put(0, -1);13    int n = nums.length;14    int ans = n;15    int cur = 0;16    for (int i = 0; i < n; ++i) {17      cur = (cur + nums[i]) % p;18      int target = (cur - k + p) % p;19      if (last.containsKey(target)) {20        ans = Math.min(ans, i - last.get(target));21      }22      last.put(cur, i);23    }24    return ans == n ? -1 : ans;25  }26}

1/** * @param {number[]} nums * @param {number} p * @return {number} */ var minSubarray =2  function (nums, p) {3    let k = 0;4    for (const x of nums) {5      k = (k + x) % p;6    }7    if (k === 0) {8      return 0;9    }10    const last = new Map();11    last.set(0, -1);12    const n = nums.length;13    let ans = n;14    let cur = 0;15    for (let i = 0; i < n; ++i) {16      cur = (cur + nums[i]) % p;17      const target = (cur - k + p) % p;18      if (last.has(target)) {19        const j = last.get(target);20        ans = Math.min(ans, i - j);21      }22      last.set(cur, i);23    }24    return ans === n ? -1 : ans;25  };

1class Solution {2public:3  int minSubarray(vector<int> &nums, int p) {4    int k = 0;5    for (int &x : nums) {6      k = (k + x) % p;7    }8    if (k == 0) {9      return 0;10    }11    unordered_map<int, int> last;12    last[0] = -1;13    int n = nums.size();14    int ans = n;15    int cur = 0;16    for (int i = 0; i < n; ++i) {17      cur = (cur + nums[i]) % p;18      int target = (cur - k + p) % p;19      if (last.count(target)) {20        ans = min(ans, i - last[target]);21      }22      last[cur] = i;23    }24    return ans == n ? -1 : ans;25  }26};

1class Solution:2    def minSubarray(self, nums: List[int], p: int) -> int: k = sum(nums) % p if k == 0: return 0 last = {0: - 1} cur = 0 ans = len(nums) for i, x in enumerate(nums): cur = (cur + x) % p target = (cur - k + p) % p if target in last: ans = min(ans, i - last[target]) last[cur] = i return - 1 if ans == len(nums) else 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 problem