1590. Make Sum Divisible by P - Detailed Explanation

Problem Statement

Description:
You are given an integer array nums and an integer p. You need to remove a (possibly empty) contiguous subarray from nums such that the sum of the remaining elements is divisible by p. In other words, if total is the sum of the entire array and sub is the sum of the removed subarray, you need:

[ \text{(total - sub)} \mod p = 0. ]

Return the minimum length of the subarray you need to remove. If it's impossible to achieve such a condition, return -1.

Important Note:

• You may remove the empty subarray if the sum of the whole array is already divisible by p.
• The subarray you remove must be contiguous.

Examples:

1. Example 1:

   • Input: nums = [3, 1, 4, 2], p = 6
   • Explanation:
     • Total sum = (3 + 1 + 4 + 2 = 10).
     • (10 \mod 6 = 4).
     • We need to remove a subarray whose sum has a remainder of (4) when divided by (6).
     • One optimal solution is to remove the subarray ([4]) (sum = 4), which leaves a sum of (3 + 1 + 2 = 6) (divisible by 6).
   • Output: 1 (length of the removed subarray is 1)

2. Example 2:

   • Input: nums = [1, 2, 3], p = 3
   • Explanation:
     • Total sum = (1 + 2 + 3 = 6).
     • (6 \mod 3 = 0).
     • No removal is needed.
   • Output: 0

3. Example 3:

   • Input: nums = [1, 2, 3], p = 7
   • Explanation:
     • Total sum = (6) and (6 \mod 7 = 6).
     • There is no contiguous subarray that you can remove to make the remaining sum divisible by 7.
   • Output: -1

Hints

• Hint 1:
  Let the total sum of the array be (S) and its remainder when divided by (p) be (r). In order for the remaining elements (after removal) to have a sum divisible by (p), the sum of the subarray you remove must have a remainder (r) when divided by (p) (because (S - \text{sub} \equiv 0 \mod p) implies (\text{sub} \equiv S \mod p)).

• Hint 2:
  Use prefix sums along with modulo arithmetic. If you define
  [ \text{prefix}[i] = \sum_{j=0}^{i} \text{nums}[j], ] then the sum of a subarray from index (i+1) to (j) is
  [ \text{prefix}[j] - \text{prefix}[i]. ] Taking modulo (p) and rearranging, you need:
  [ \text{prefix}[j] \mod p - \text{prefix}[i] \mod p \equiv r \mod p. ] This observation enables you to efficiently find candidate subarrays using a hash map that stores the latest index for each modulo value.

Approaches

Approach: Prefix Sum with Hash Map (Optimal)

Intuition

1. Compute Total Remainder:
   Let (S) be the total sum of the array. Calculate (r = S \mod p).

   • If (r = 0), the entire array is already divisible by (p); return 0.

2. Prefix Sum Modulo:
   As you iterate over the array, compute the running prefix sum modulo (p) (denoted as curr_mod).

   • For a prefix ending at index (j) with modulo value curr_mod, you want to find a previous prefix (say at index (i)) such that: [ (\text{curr\_mod} - \text{prev\_mod} + p) \mod p = r. ]
   • Rearranging gives:
     [ \text{prev\_mod} = (\text{curr\_mod} - r + p) \mod p. ]

3. Use Hash Map:
   Use a dictionary (or hash map) to store the latest index where each modulo value is seen.

   • Initialize the dictionary with {0: -1} so that if the prefix sum itself gives the desired remainder, you can remove a prefix from the start.
   • As you traverse, update the dictionary and check for candidates that yield the minimum subarray length.

4. Answer Determination:
   The minimal subarray length is updated whenever a valid candidate is found. If no valid candidate is found that is shorter than the length of the array, return -1.

Pseudocode

function minSubarray(nums, p):
    total = sum(nums)
    r = total mod p
    if r == 0: return 0

    prefix_mod = 0
    hashmap = {0: -1}
    min_length = infinity

    for i from 0 to length(nums)-1:
        prefix_mod = (prefix_mod + nums[i]) mod p
        target = (prefix_mod - r + p) mod p
        if target in hashmap:
            min_length = min(min_length, i - hashmap[target])
        hashmap[prefix_mod] = i

    return min_length if min_length < length(nums) else -1

Code Examples

Python Code