#1590

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Make Sum Divisible by P

Determine the minimum-length subarray to remove so the remaining array sum is divisible by a given integer p efficiently.

array hash table prefix sum

Problem Statement

Given an array of positive integers nums and a positive integer p, remove the shortest contiguous subarray such that the sum of the remaining elements is divisible by p. The subarray removed cannot be the entire array.

Return the length of this smallest subarray. If no such subarray exists, return -1. A subarray is defined as a continuous block of elements within nums.

Examples

Example 1

Input: nums = [3,1,4,2], p = 6

Output: 1

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

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

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

Solution Approach

Compute Total Modulo

First, calculate the total sum of nums modulo p. If it is already zero, return 0 immediately since no removal is needed. This sets the target remainder that must be balanced by removing a subarray.

Use Prefix Sums with Hash Map

Maintain a running prefix sum modulo p and store each modulo index in a hash map. For each position, check if removing a subarray ending at the current index can offset the total remainder. This allows O(1) lookups for candidate subarrays while scanning the array once.

Track Minimum Subarray Length

Whenever a valid subarray is identified that balances the total sum modulo p, compute its length and update the minimum found. After scanning the array, return the minimum length or -1 if no valid subarray exists.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The algorithm runs in O(n) time since it scans the array once while maintaining a hash map of modulo indices. Space complexity is O(n) to store the prefix sum remainders in the hash map, which grows linearly with the array length.

What Interviewers Usually Probe

Do you know how to use prefix sums to avoid checking every subarray explicitly?
Can you leverage modulo arithmetic with a hash map to identify candidate subarrays efficiently?
Think about edge cases where the array sum is already divisible by p or where no subarray can satisfy the condition.

Common Pitfalls or Variants

Common pitfalls

Forgetting that removing the entire array is not allowed can lead to incorrect -1 handling.
Not using modulo operation on prefix sums can result in overflow or incorrect subarray matches.
Failing to update the minimum subarray length correctly when multiple candidates exist can return the wrong answer.

Follow-up variants

Instead of the smallest subarray, find the largest subarray that must be removed to achieve divisibility by p.
Allow removal of multiple non-contiguous elements to make the sum divisible by p, requiring a different hashing strategy.
Solve the problem when p is not fixed but given as a list of possible divisors to test for each.

FAQ

What is the main strategy for Make Sum Divisible by P?

Use prefix sums combined with a hash map to track remainders modulo p, allowing efficient identification of minimal subarrays to remove.

Can the entire array be removed to satisfy divisibility?

No, the problem explicitly forbids removing the entire array; at least one element must remain.

How do I handle cases where the array sum is already divisible by p?

Return 0 immediately since no subarray removal is necessary when the total sum modulo p is zero.

What is the time complexity of this approach?

The solution runs in O(n) time, scanning the array once and using a hash map for constant-time remainder lookups.

Are there pitfalls with large numbers in nums or p?

Yes, always compute prefix sums modulo p to avoid integer overflow and ensure correct subarray remainder calculations.

terminal

Solution

Solution 1: Prefix Sum + Hash Table

First, we calculate the sum of all elements in the array $\textit{nums}$ modulo $p$, denoted as $k$. If $k$ is $0$, it means the sum of all elements in the array $\textit{nums}$ is a multiple of $p$, so we directly return $0$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    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

Continue Practicing

#1546 maximum number of non overlapping subarrays with sum equals target #1658 minimum operations to reduce x to zero #1674 minimum moves to make array complementary