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
- Let
totalbe the sum ofnumsandrem = total % p. Ifrem == 0, no removal is needed, so the answer is 0. - Removing a subarray whose sum is congruent to
remmodulopmakes the remainder divisible byp. So we need the shortest subarray withsum % p == rem. - Sweep with prefix sums modulo
p, storing the earliest index at which each residue was seen. - 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 isbest < n. Getting this boundary wrong flips the-1case. - Using
cur - remwithout 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.