Continuous Sub Array Sum (Leet Code)

Pretty much every software engineer who wants to enhance their problem-solving skills for interviews (yes there is a difference between interviews these days and problem solving at work daily) looks into problems at Leet Code. I was looking at this problem and it is more of a math's problem actually than programming.

(18) Continuous Subarray Sum — LeetCode

So, question is that in an array find a sub array where sum of the elements in sub array is equal to some multiple of a given sum (K).

Before we jump into this problem, let’s take a simpler one: in array of integers find sub array where sum of elements in the sub array is equal to given sum (K). Which means we have to find two index i and j such that a[i] + a[i+1]… + a[j ] = K.

To solve this problem, we can use running sum of array for each index, so if Si denotes sum of the array from index 0 to i, then we need to find two indexes i and j such that Sj — Si = K. So, at each index we calculate the running sum and store it in map. Then while traversing the array for every index j we check if Sj — k is present in map. If we find the entry in map, then we can say that there exists a sub array whose element’s sum is equal to K.

Now to extend the problem here, we have to find two index i, j such that Sj — Si = m*K, where m is some integer multiplier. So, storing Si at each index in the map will not help here, just like it did in previous version of problem.

For this problem, let’s split our equation Sj — Si = m*K a bit. Let’s say we divide each Si with K and find a modulo (i.e. Si%K), so we can write the above equation as:

Any Si can be written as (x*K + a), i.e. Si%K = a. Transforming Si and Sj in this way will transform the equation to:

(x*K + a) — (y*K + b) = m*K ==> (x-y)*K + (a-b) = m*K

Now, remember that a and b were modulo (Sj%k and Si%k). So, both a and b must of less than K. With that (a-b) should also be less than K. Now if a and b have to satisfy highlighted equation above, then a-b can only be 0 or some multiple of K but since it is supposed to be less then K, it can only be 0. Which means a == b. Which means at each index instead of storing Si, store Si % K in the map. And when we find an index j such that Sj%K is already in map we find the answer.

With that below C++ code is one solution to the problem. One thing to note here below is that at each index i, we don’t store the Si%K in the set, instead the code below is storing the previous value i.e. Si-1%K. This is because the problem mentions that we have to find a subarray with at least two items in it.

bool checkSubarraySum(vector<int>& n, int k) 
    {
        unordered_set<int> _remainders;
        int prevRemainder = 0;
        int s = 0;
        
        for (int i = 0; i < n.size(); i++)
        {
            s += n[i];
            
            int remainder = k == 0 ? s : s % k;
                        
            if (_remainders.count(remainder) != 0) return true;
            
            
            _remainders.insert(prevRemainder);
            prevRemainder = remainder;
        }
        
       
        return false;
        
    }