Problem
Given an array of positive integers nums
, remove the smallest subarray (possibly empty) such that the sum of the remaining elements is divisible by p
. It is not allowed to remove the whole array.
Return the length of the smallest subarray that you need to remove, or -1
if it’s impossible.
A subarray is defined as a contiguous block of elements in the array.
Examples
Example 1:
|
|
Example 2:
|
|
Example 3:
|
|
Solution
Method 1 - Prefix sum
Here is the strategy:
- Total Sum and Remainder: Calculate the total sum of the array, and find the remainder when the total sum is divided by
p
. The remainder gives us the amount we need to adjust in the remaining array to make it divisible byp
. - Prefix Sums and Modulo Map: Use a prefix sum and a dictionary to keep track of seen remainders and their corresponding indices. This helps us quickly determine the shortest subarray whose removal will adjust the total sum to be divisible by
p
.
Here are the steps:
- Compute the total sum and its remainder modulo
p
(denoted astotal_sum % p
). - If the remainder is
0
, the total sum is already divisible byp
, so return0
. - Iterate through the array to calculate the prefix sums while keeping track of the remainders modulo
p
and their indices. - For each prefix sum’s remainder, check if there was a previously seen remainder that would make the total sum divisible by
p
. - Track the minimum subarray length encountered during the iteration.
Derivation
$$ \text{nums} = [a_1, a_2, \ldots, a_j, \ldots, a_{n-1}] $$
Let sum of nums be denoted by alpha (α). And prefix sums be denoted by array F.
Step 1 - Calculate the remainder
$$
r = sum(nums) % p
$$
if r == 0
⇨ return 0., as we already satisfy given condition.
Step 2 - Find the smallest nums[i..j]
We want the smallest subarray, nums[i:j]
, such that:
$$ (sum(nums) \text{ - } \text{sum(nums[i:j])}) \text{ % p } = 0 \tag{1} $$
$$ \implies sum(nums[i:j]) %\ p = sum(nums)\ %\ p $$
sum(nums[i:j])
can be represented in terms of prefix sums as: F[j] - F[i]
. We hope there is some prefix sum F[i]=sum(arr[0...i]))
such that: sum(arr[i...j]) == (F[j] - F[i]) % p== target
where target
is the remainder we want to get rid of i.e. r
For nums = [1, 2, 3]
:
- Prefix sums ( F ) can be calculated as:
F = [0, 1, 3, 6]
F[0] = 0
F[1] = F[0] + 1 = 1
F[2] = F[1] + 2 = 3
F[3] = F[2] + 3 = 6
- sum(
nums[0:2]
) =F[2] - F[0]
= ( 1 + 2 = 3 )
So, we can rewrite above equation 1 as:
$$
sum(nums) - (F[j] - F[i]) = n \cdot p
$$
where n
is some integer.
We can rewrite it as: $$ F[j] - F[i] = sum(nums) - n \cdot p \tag{2} $$
Mod both sides by ( p ): $$ (F[j] - F[i])\ %\ p = (\alpha - n \cdot p)\ %\ p $$
Apply the distributive law of mods: $$ (a + b) % c = ((a % c) + (b % c)) % c $$
$$ (F[j] - F[i])\ %\ p = (\alpha % p - (n \cdot p) % p) % p $$
Since ( (n . p) % p = 0 ): $$ (F[j] - F[i]) % p = (\alpha % p) % p $$
Thus: $$ (F[j] - F[i]) % p = r $$
or: $$ F[j] - F[i] = n \cdot p + r $$
where ( n ) is an integer and ( r =α % p ).
Rewriting the expression for ( F[i] ): $$ F[i] = F[j] - n \cdot p - r $$
Mod both sides by ( p ): $$ F[i] % p = (F[j] - n \cdot p - r) % p $$
Since ( n.p % p = 0
):
$$ F[i] % p = (F[j] % p - r % p) % p $$
Code
|
|
|
|
Complexity
- ⏰ Time complexity:
O(n)
, wheren
is number of elements in nums array, because we iterate through the array once to calculate prefix sums and once again to check the prefix sums in the map. - 🧺 Space complexity:
O(n)
, because we use a hash map to store the prefix sums and their corresponding indices.