1590. Make Sum Divisible by P¶

Description¶

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.

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.

Constraints

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹
1 <= p <= 10⁹

Solution: Brute Force¶

The brute force solution is to find all the possible subarrays and check if the sum of the subarray is divisible by p. If it is divisible, then we can remove that subarray and return the length of the subarray.

First, we need to find the total sum of the array. If the total sum is already divisible by p, then we do not need to remove any subarray. So, we can return 0.

Else, we iterate through the array and get the sum by deducting the total sum of subarray from the total sum and check if the sum is divisible by p. If it is divisible, then we know that the subarray is removable. In order to confirm the which removable subarrays have the smallest length, we will keep track with smallest variable which stores the minimum length of the all removable subarrays.

Finally, we return the smallest variable which contains the minimum length of the removable subarray. But if the smallest variable is not updated, it means all combinations are not divisible by p. So, we return -1.

Time Complexity: O(n²)
- where n is the length of the nums array
Space Complexity: O(1)
- The variables like totalSum , smallest, subArraySum which are not dependent on the input size. So, the algorithm use constant amount of space.

Time Limit Exceeded

By using this approach, we will face Time Limit Exceeded error for the given constraints 10⁵.

TypeScript

function minSubarray(nums: number[], p: number): number {
    let totalSum = 0;

    for (let i = 0; i < nums.length; i++) {
        totalSum += nums[i];
    }

    if (totalSum % p == 0) return 0;

    let smallest = nums.length;

    for (let start = 0; start < nums.length; start++) {
        let subArraySum = 0;
        for (let end = start; end < nums.length; end++) {
            subArraySum += nums[end];

            if ((totalSum - subArraySum) % p == 0) {
                smallest = Math.min(smallest, end - start + 1);
            }
        }
    }

    return smallest == nums.length ? -1 : smallest;
};

Solution: Prefix Sum¶

As sum(i, j) = sum(0, j) - sum(0, i), we can use the prefix sum to find the sum of the subarray in O(1) time. Instead of finding each subarray sum like in the brute force solution, we can find the prefix sum of the array and store it in a hash table. For each hash value, we can get the smallest subarray by checking the difference between the total sum and the prefix sum.

Time Complexity: O(n)
- where n is the length of the nums array
Space Complexity: O(n)
- using a hash table to store the prefix sum of the array.

TypeScript

function minSubarray(nums: number[], p: number): number {

    let totalSum = 0;

    for (let i = 0; i < nums.length; i++) {
        totalSum += nums[i];
    }

    let target = totalSum % p;
    if (target == 0) return 0;

    let modMap = new Map<number, number>();
    modMap.set(0, -1);

    let prefixSum = 0;
    let smallest = nums.length;

    for (let i = 0; i < nums.length; i++) {

        prefixSum = (prefixSum + nums[i]) % p;

        /// Calculate the diff between `prefixSum` and `target`
        /// If the diff is negative, we add `p` to make it positive
        let targetMod = (prefixSum - target + p) % p;

        if (modMap.has(targetMod)) {
            smallest = Math.min(smallest, i - modMap.get(targetMod)!);
        }

        modMap.set(prefixSum, i);
    }

    return smallest == nums.length ? -1 : smallest;
};

modular function

A concept of how to get modular / mod without % operator.

TypeScript

function _mod(a: number, b: number): number {
    if (b === 0) throw new Error("Division by zero");

    // Handle negative numbers
    const isNegative = a < 0;
    a = Math.abs(a);
    b = Math.abs(b);

    // Compute modulo
    while (a >= b) {
        a -= b;
    }

    // Preserve sign of dividend
    return isNegative ? -a : a;
}