Medium

Make Sum Divisible by P

LAB

Remove the shortest non-empty subarray so the remaining sum is divisible by p. Return -1 if impossible.

EXAMPLES

Example 1

Input
{
  "nums": [
    3,
    1,
    4,
    2
  ],
  "p": 6
}

Output
1

FUNCTION SHAPE

nums: intArrayp: int→int

SOLUTION NOTE

The diagram:

textEXAMPLE

# [       pref_sum % p           ]
# [    (pref_sum-k)%p ][k%p]
# [                   k % p                     ]

We want the LATEST INDEX of prefix subarray that has mod (a-k)%p, since this will minimize the length of the (k%p) subarray.

Searching for (pref_sum - k) % p will carve out a subarray of sum k % p, which when removed leaves sum 0 % p.

Reveal reference solution +

pythonREFERENCE

def minSubarray(self, nums: List[int], p: int) -> int:
    k = sum(nums) % p
    if k == 0:
        return 0  # edge case

    n = len(nums)
    prefsum_to_index = {0: -1}
    pref_sum = 0
    res = inf

    for i in range(n):
        pref_sum = (pref_sum + nums[i]) % p
        if (pref_sum - k) % p in prefsum_to_index:
            res = min(res, i - prefsum_to_index[(pref_sum - k) % p])
        prefsum_to_index[pref_sum] = i

    return res if res != n else -1

TimeO(n)

SpaceO(n)

Open on LeetCode ↗