LeetCode 1590 - Make Sum Divisible by P

This problem asks us to determine the smallest contiguous subarray we can remove from a given array of positive integers

leetcodemediumarrayhash-tableprefix-sum

LeetCode Problem 1590

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Prefix Sum

Solution

Problem Understanding

This problem asks us to determine the smallest contiguous subarray we can remove from a given array of positive integers, nums, so that the sum of the remaining elements becomes divisible by a given integer p. The key here is that the subarray must be contiguous, and it cannot be the entire array. If the sum of the array is already divisible by p, then we do not need to remove anything, and the answer is zero. If it is impossible to make the sum divisible by p by removing a subarray, the function should return -1.

The input nums can be very large, up to 100,000 elements, and each number in the array can be as large as 10^9. Similarly, p can be as large as 10^9. This tells us that a brute-force approach that examines all possible subarrays will be too slow due to the O(n^2) or O(n^3) time complexity that could result from nested loops.

Important edge cases include when the sum is already divisible by p, when no subarray can make the sum divisible, when removing a single element is sufficient, and when the subarray to remove is at the start or end of the array.

Approaches

The brute-force approach involves iterating through all possible subarrays, calculating the sum of the remaining elements after removing each subarray, and checking divisibility by p. While this approach is straightforward and guarantees correctness, it is highly inefficient for large arrays because it would require O(n^2) or O(n^3) operations, which is not feasible for n up to 10^5.

The optimal approach uses prefix sums combined with a hash map to track remainders modulo p. The key insight is that we only need to consider subarrays whose sum modulo p matches a specific value derived from the total sum modulo p. Let the total sum of the array modulo p be total_mod = sum(nums) % p. To remove a subarray and make the sum divisible by p, the sum of the subarray modulo p must equal total_mod. By maintaining a hash map of prefix sums modulo p to their latest index, we can efficiently determine the length of the subarray to remove in O(n) time.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(1) Checks every subarray; too slow for large n
Optimal O(n) O(n) Uses prefix sums and hash map to find the shortest subarray efficiently

Algorithm Walkthrough

  1. Compute the total sum of nums modulo p and store it in total_mod. If total_mod is zero, the sum is already divisible by p, so return 0 immediately.
  2. Initialize a hash map mod_index to store the last index where each prefix sum modulo p occurs. Prepopulate it with {0: -1} to handle subarrays starting at index 0.
  3. Initialize prefix_mod = 0 and min_length = n + 1, where n is the length of the array.
  4. Iterate through the array using index i and value num:

a. Update the prefix sum modulo p using prefix_mod = (prefix_mod + num) % p.

b. Calculate the target modulo we need to find in the hash map: target = (prefix_mod - total_mod + p) % p. This accounts for negative differences modulo p.

c. If target exists in mod_index, update min_length with the length of the subarray to remove: i - mod_index[target].

d. Update the hash map with the current prefix modulo: mod_index[prefix_mod] = i. 5. After iteration, if min_length is less than n, return it. Otherwise, return -1 because removing the entire array is not allowed.

Why it works: The algorithm works because we are looking for a subarray whose sum modulo p equals total_mod. By using prefix sums and a hash map, we efficiently track previous prefix sums modulo p and find the shortest valid subarray in a single pass. The invariant is that for any index i, prefix_mod[i] - prefix_mod[j] modulo p gives the sum of the subarray nums[j+1..i] modulo p.

Python Solution

from typing import List

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        total_mod = sum(nums) % p
        if total_mod == 0:
            return 0
        
        mod_index = {0: -1}
        prefix_mod = 0
        min_length = len(nums) + 1
        
        for i, num in enumerate(nums):
            prefix_mod = (prefix_mod + num) % p
            target = (prefix_mod - total_mod + p) % p
            if target in mod_index:
                min_length = min(min_length, i - mod_index[target])
            mod_index[prefix_mod] = i
        
        return min_length if min_length < len(nums) else -1

The Python implementation follows the algorithm exactly. We first calculate total_mod and handle the case where no removal is needed. The mod_index dictionary stores the last seen index of each prefix modulo, and we update min_length whenever a valid subarray is found. Finally, we check whether the minimum length is valid before returning.

Go Solution

func minSubarray(nums []int, p int) int {
    totalSum := 0
    for _, num := range nums {
        totalSum += num
    }
    totalMod := totalSum % p
    if totalMod == 0 {
        return 0
    }
    
    modIndex := map[int]int{0: -1}
    prefixMod := 0
    minLength := len(nums) + 1
    
    for i, num := range nums {
        prefixMod = (prefixMod + num) % p
        target := (prefixMod - totalMod + p) % p
        if idx, exists := modIndex[target]; exists {
            if i - idx < minLength {
                minLength = i - idx
            }
        }
        modIndex[prefixMod] = i
    }
    
    if minLength < len(nums) {
        return minLength
    }
    return -1
}

The Go implementation mirrors the Python solution. We explicitly handle the index map with integer keys and values. Go does not have built-in negative modulo correction, so we ensure target is positive. Slice indexing and map lookups replace Python dictionary operations.

Worked Examples

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

total_mod = (3+1+4+2) % 6 = 10 % 6 = 4

We need to remove a subarray whose sum modulo 6 is 4.

i num prefix_mod target mod_index min_length
0 3 3 (3-4+6)%6=5 {0:-1} 7
1 1 4 (4-4+6)%6=6%6=0 {0:-1,3:0} i - (-1) = 2
2 4 2 (2-4+6)%6=4 {0:-1,3:0,4:1} 2
3 2 4 (4-4+6)%6=0 {0:-1,3:0,4:2} i - (-1)=4

Minimum valid length is 1 (removing [4]).

Example 2: nums = [6,3,5,2], p = 9

total_mod = (6+3+5+2)%9 = 16%9 = 7

Target subarray sum modulo = 7. Following the algorithm, the shortest subarray is [5,2] with length 2.

Example 3: nums = [1,2,3], p = 3

total_mod = 6 % 3 = 0

No removal needed, return 0.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass through array, with constant time map operations
Space O(n) Hash map stores at most n prefix sums modulo p

The time complexity is linear because we only iterate once over the array. The space complexity is linear due to storing prefix sums modulo p in the hash map.

Test Cases

# Provided examples
assert Solution().minSubarray([3,1,4,2], 6) == 1  # remove [4]
assert Solution().minSubarray([6,3,5,2], 9) == 2  # remove [5,2]
assert Solution().minSubarray([1,2,3], 3) == 0    # already divisible

# Edge cases
assert Solution().minSubarray([1], 2) == -1       # cannot