[LeetCode] 1590. Make Sum Divisible by p

Problem

Image is linked to LeetCode problem page

Explanation

We are given an array `[x_0,x_1,x_2,\dots ,x_{n-1}] ,` and a positive integer `p`. Let `S` represent the total sum of the array and `R` the total remainder, defined as `R = S \bmod p.` Our goal is to remove one contiguous subarray `[x_i,\dots ,x_j]` such that the remaining sum is divisible by `p`: ``(S-(x_i + \cdots + x_j)) \bmod p = 0.``This condition is equivalent to `` (x_i + \cdots + x_j) \bmod p = R.`` So the task reduces to finding the shortest subarray whose sum modulo `p` equals `R`. 

To efficiently compute subarray sums, we use prefix sums modulo `p`. Define `P_k` as the remainder of the sum of all elements from the beginning of the array up to index `k`: 

``P_{k} = (x_0 + \dots + x_{k}) \bmod p``

To prevent integer overflow when dealing with large values, we can compute these incrementally using `P_k = (P_{k-1} + x_k)%p`. This allows us to maintain the running remainder without needing to store the actual cumulative sum of the array. 

 

For any subarray `[x_i,\dots ,x_j]` its sum modulo `p` can be computed using prefix sums: ``(x_i + \cdots + x_j) \bmod p = ((x_0 + \cdots + x_j) - (x_0 + \cdots + x_{i-1})) \bmod p = (P_j - P_{i-1}) \bmod p ``

We want this value to equal `R`, so we write: ``(P_j - P_{i-1} +p) \bmod p = R.``

Rearranging the equation gives: ``P_{i-1} = (P_j - R + p) \bmod p.``

The addition of `p` ensures the value is non-negative before applying modulo. In C++, the ##%## operator computes a remainder, not a true mathematical modulo, and can return negative values when the left operand is negative (for example, ##-1 % 7 = -1## when mathematically `-1 \bmod 7 = 6`). 

 

Thus, for each `P_j`, we need to check if the required `P_{i-1}` has been encountered previously. To perform this check in `O(1)` time, we store the values in a hash map where the key is the prefix sums modulo and the value is the index of its most recent occurence. The algorithm follows these steps: 

1. Initialize a hash map with the entry ##{0, -1}##. This handles the case where `P_{-1}=0`, allowing us to identify and handle subarrays that begin at index 0. 
2. Iterate through the array, updating the current prefix sum modulo `p` at each step `j`. 
3. If `P_{i-1}` exists in the map, calculate the length of the candidate subarray `j - map[P_{i-1}]` and update the minimum length found so far
4. Update map with current index `j` for the key value `P_j` to ensure we will be using the most recent index for future checks to minimize distance. 
5. If the minimum length remains equal to the original array length after a full iteration, conclude that no such subarray exists and return `-1`. 

Solution

#include <vector>
#include <unordered_map>
#include <algorithm>

class Solution {
public:
    int minSubarray(vector<int>& nums, int p) {
        int n = nums.size();
        int R = 0;
        for(int x: nums) R = (R + x) % p;
        if(R == 0) return 0;
        
        std::unordered_map<int, int> prefix = {{0, -1}};
        int P_curr = 0;
        int ans = n;
        for(int j=0; j<n; j++) {
            P_curr = (P_curr + nums[j]) % p;
            int P_prev = (P_curr - R + p)%p;
            if(prefix.count(P_prev)) {
                ans = std::min(ans, j - prefix[P_prev]);
            }
            prefix[P_curr] = j;
        }
        if (ans == n) return -1;
        return ans;
    }
};