1590. Make Sum Divisible by P

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 <= 105
• 1 <= nums[i] <= 109
• 1 <= p <= 109

Approach 01:

#include <algorithm>
#include <numeric>
#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
public:
    int minSubarray(vector<int>& nums, int p) {
        const long totalSum = accumulate(nums.begin(), nums.end(), 0L);
        const int remainder = totalSum % p;
        if (remainder == 0)
            return 0;

        unordered_map<int, int> prefixToIndex{{0, -1}};
        int minLength = nums.size();
        int prefixSum = 0;

        for (int i = 0; i < nums.size(); ++i) {
            prefixSum += nums[i];
            prefixSum %= p;
            const int target = (prefixSum - remainder + p) % p;
            if (const auto it = prefixToIndex.find(target);
                it != prefixToIndex.cend())
                minLength = min(minLength, i - it->second);
            prefixToIndex[prefixSum] = i;
        }

        return minLength == nums.size() ? -1 : minLength;
    }
};

from itertools import accumulate

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        totalSum = sum(nums)
        remainder = totalSum % p
        if remainder == 0:
            return 0

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

        for i, num in enumerate(nums):
            prefixSum += num
            prefixSum %= p
            target = (prefixSum - remainder + p) % p
            if target in prefixToIndex:
                minLength = min(minLength, i - prefixToIndex[target])
            prefixToIndex[prefixSum] = i

        return -1 if minLength == len(nums) else minLength

Time Complexity

• Calculating the total sum:

  The function starts by calculating the total sum of the input vector nums. This requires iterating through all the elements of the array, which takes \(O(n)\), where \(n\) is the size of the input array.

• Iterating through the array:

  In the main loop, the function iterates through all elements of the array once to compute the prefix sum and update the hash map. This step also takes \(O(n)\).

• Hash map operations:

  Looking up and inserting elements in the unordered map prefixToIndex takes \(O(1)\) on average. Since these operations are performed in each iteration of the loop, this contributes to the overall \(O(n)\) complexity of the loop.

• Overall Time Complexity:

  The overall time complexity is \(O(n)\), where \(n\) is the size of the input array.

Space Complexity

• Auxiliary Space:

  The function uses an unordered map prefixToIndex to store the prefix sums and their corresponding indices. In the worst case, this map could store up to \(n + 1\) elements (including the initial value), where \(n\) is the size of the input array. Thus, the space complexity of the map is \(O(n)\).

• Overall Space Complexity:

  The overall space complexity is \(O(n)\), where \(n\) is the size of the input array.