1590. Make Sum Divisible by P

Description

Given an array of integers nums and an integer p, the task is to find the length of the smallest subarray that can be removed so that the sum of the remaining elements is divisible by p. If no such subarray exists, return -1.

Intuition

The sum of the entire array is calculated first, and the goal is to find the shortest subarray that would make the remainder of the sum divisible by p. By maintaining prefix sums and calculating remainders using the modulo operator, we can determine if removing a subarray can achieve this condition.

Approach

1. Calculate the total sum of the array: First, find the remainder of the sum modulo p.
2. Edge case: If the remainder is 0, the array is already divisible by p, so return 0.
3. Prefix sum and target remainder: Iterate through the array while maintaining a running prefix sum. At each step, calculate the current prefix sum modulo p and check if a previously seen prefix sum exists that can help form a valid subarray.
4. Map storage: Store the prefix sums in a map to keep track of the indices where the sums occurred.
5. Result: If a valid subarray is found, calculate its length and return the minimum length found. If no such subarray is possible, return -1.

Complexity

• Time Complexity: O(n), where n is the length of the array. Each element is processed once to calculate the prefix sums and the required subarray.
• Space Complexity: O(n) for storing the prefix sums in a map.

Code

C++

class Solution {
public:
    int minSubarray(vector& nums, int p) {
        long long totalSum = accumulate(nums.begin(), nums.end(), 0LL);  // Use 0LL to force long long

        int remainder = totalSum % p;

        if (remainder == 0)
            return 0;

        int n = nums.size();
        int minLength = n;
        int prefixSum = 0;
        unordered_map prefixSums;

        prefixSums[0] = -1;

        for (int i = 0; i < n; i++) {
            prefixSum = (prefixSum + nums[i]) % p;
            int target = (prefixSum - remainder + p) % p;

            if (prefixSums.find(target) != prefixSums.end()) {
                minLength = min(minLength, i - prefixSums[target]);
            }

            prefixSums[prefixSum] = i;
        }

        return minLength == n ? -1 : minLength;
    }
};

Python

class Solution:
    def minSubarray(self, nums, p):
        totalSum = sum(nums)
        remainder = totalSum % p

        if remainder == 0:
            return 0

        n = len(nums)
        minLength = n
        prefixSum = 0
        prefixSums = {0: -1}

        for i in range(n):
            prefixSum = (prefixSum + nums[i]) % p
            target = (prefixSum - remainder + p) % p

            if target in prefixSums:
                minLength = min(minLength, i - prefixSums[target])

            prefixSums[prefixSum] = i

        return minLength if minLength < n else -1

Java

public class Solution {
    public int minSubarray(int[] nums, int p) {
        long totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

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

        HashMap prefixSums = new HashMap<>();
        prefixSums.put(0, -1);

        int n = nums.length;
        int prefixSum = 0;
        int minLength = n;

        for (int i = 0; i < n; i++) {
            prefixSum = (prefixSum + nums[i]) % p;
            if (prefixSum < 0) {
                prefixSum += p;  // Adjust for negative remainders
            }

            int target = (prefixSum - remainder + p) % p;
            if (prefixSums.containsKey(target)) {
                minLength = Math.min(minLength, i - prefixSums.get(target));
            }

            prefixSums.put(prefixSum, i);
        }

        return minLength == n ? -1 : minLength;
    }
}

JavaScript

function minSubarray(nums, p) {
    const totalSum = nums.reduce((acc, num) => acc + num, 0);
    const remainder = totalSum % p;

    if (remainder === 0) return 0;

    const n = nums.length;
    let minLength = n;
    let prefixSum = 0;
    const prefixSums = new Map();

    prefixSums.set(0, -1);

    for (let i = 0; i < n; i++) {
        prefixSum = (prefixSum + nums[i]) % p;
        const target = (prefixSum - remainder + p) % p;

        if (prefixSums.has(target)) {
            minLength = Math.min(minLength, i - prefixSums.get(target));
        }

        prefixSums.set(prefixSum, i);
    }

    return minLength === n ? -1 : minLength;
}