⚡Flashcard Drill➔
NeetCode #113LC-1590MediumArrays & Hashing
← Back to All Problems

#113 · #1590 · Make Sum Divisible by P(使数组和能被 P 整除)

📌 Problem Statement & Constraints

Given an array of positive integers nums and an integer p, remove the shortest subarray (possibly empty) so that the sum of the remaining elements is divisible by p. Return the length of the shortest such subarray, or -1 if impossible. Constraints: 1 <= nums.length <= 10^5, 1 <= nums[i] <= 10^9, 1 <= p <= 10^9.

💡 Core Algorithmic Approaches

  1. Let total be the sum of nums and rem = total % p. If rem == 0, no removal is needed, so the answer is 0.
  2. Removing a subarray whose sum is congruent to rem modulo p makes the remainder divisible by p. So we need the shortest subarray with sum % p == rem.
  3. Sweep with prefix sums modulo p, storing the earliest index at which each residue was seen.
  4. For each position, look up the residue (cur - rem) % p; if seen, the gap is a candidate answer. Keeping only the earliest occurrence maximises the gap and hence minimises the removed length.

💻 Benchmark Python3 Implementation

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        total = sum(nums)
        rem = total % p
        if rem == 0:
            return 0                       # already divisible
        first = {0: -1}                    # residue -> earliest prefix index
        cur = 0
        n = len(nums)
        best = n
        for i, x in enumerate(nums):
            cur = (cur + x) % p
            need = (cur - rem) % p
            if need in first:
                best = min(best, i - first[need])
            if cur not in first:           # keep only the earliest occurrence
                first[cur] = i
        return best if best < n else -1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass with O(1) average hash operations.
💾 Space Complexity
O(min(n, p)) for the residue-to-index map.

⚠️ Interview Pitfalls & Follow-ups

  • Overwriting first[cur] on every occurrence: keeping the latest index would minimise the gap instead of maximising it. Only record the first.
  • Removing the whole array: if the only valid removal is the entire array, the remaining sum is 0, which is divisible by p -- but the problem requires a non-empty remainder, so the check is best < n. Getting this boundary wrong flips the -1 case.
  • Using cur - rem without the modulo normalisation: negative residues would never match a stored key.
  • Assuming the answer is n - longest: the framing is equivalent but the direct shortest-subarray search is cleaner.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems