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:

Input: nums = [3,1,4,2], p = 6
Output: 1
Explanation: The sum of the elements in nums is 10, which is not divisible by 6. We can remove the subarray [4], and the sum of the remaining elements is 6, which is divisible by 6.

Example 2:

Input: nums = [6,3,5,2], p = 9
Output: 2
Explanation: We cannot remove a single element to get a sum divisible by 9. The best way is to remove the subarray [5,2], leaving us with [6,3] with sum 9.

Example 3:

Input: nums = [1,2,3], p = 3
Output: 0
Explanation: Here the sum is 6. which is already divisible by 3. Thus we do not need to remove anything.

Solution

Method 1 - Prefix sum

Here is the strategy:

  1. 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 by p.
  2. 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:

  1. Compute the total sum and its remainder modulo p (denoted as total_sum % p).
  2. If the remainder is 0, the total sum is already divisible by p, so return 0.
  3. Iterate through the array to calculate the prefix sums while keeping track of the remainders modulo p and their indices.
  4. For each prefix sum’s remainder, check if there was a previously seen remainder that would make the total sum divisible by p.
  5. 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

Java
class Solution {
    public int minSubarray(int[] nums, int p) {
        // Calculate the total remainder when the sum of the array is divided by
        // p
        int tgtRem = 0;
        for (int num : nums) {
            tgtRem = (tgtRem + num) % p;
        }

        // If the remainder is 0, the sum is already divisible by p, so return 0
        if (tgtRem == 0) {
            return 0;
        }

        // Initialize prefix sum and a hashmap to store prefix sums and their
        // indices
        int prefixSum = 0;
        Map<Integer, Integer> prefixMap = new HashMap<>();
        // Base case: handle the situation where removing the prefix makes the
        // sum divisible
        prefixMap.put(0, -1);

        // Variable to store the minimum length of the subarray to be removed
        int minLen = Integer.MAX_VALUE;

        // Iterate through the array to compute prefix sums
        for (int i = 0; i < nums.length; i++) {
            // Update the prefix sum
            prefixSum = (prefixSum + nums[i]) % p;

            // Calculate the needed remainder to find a valid subarray
            int neededRem = (prefixSum - tgtRem + p) % p;

            // If the needed remainder is already in the prefixMap
            if (prefixMap.containsKey(neededRem)) {
                // Calculate the length of the subarray to remove
                minLen = Math.min(minLen, i - prefixMap.get(neededRem));
            }

            // Update the prefixMap with the current prefix sum and its index
            prefixMap.put(prefixSum, i);
        }

        // If we have found a valid subarray, return its length; otherwise,
        // return -1
        return minLen < nums.length ? minLen : -1;
    }
}
Python
class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        total_sum = sum(nums)
        target_remainder = total_sum % p

        if target_remainder == 0:
            return 0

        prefix_sum = 0
        prefix_map = {
            0: -1
        }  # To handle the case when the prefix itself is a valid subarray to remove
        min_length = float("inf")

        for i, num in enumerate(nums):
            prefix_sum = (prefix_sum + num) % p
            needed_remainder = (prefix_sum - target_remainder) % p
            if needed_remainder in prefix_map:
                min_length = min(min_length, i - prefix_map[needed_remainder])
            prefix_map[prefix_sum] = i

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

Complexity

  • ⏰ Time complexity: O(n), where n 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.