# Share my O(n) C++ accumulation-modulo solution with thinking process and explanation

• ## 1. Problem

Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer

## 2. Thinking process

#### 2.1 Calculate the summation of a continuous subarray

As we know the summation of series

#### S(n) = a(1) + a(2) + ... + a(n), n ≥ 1

which has a recursion formula

#### S(n) = a(n) + S(n - 1), n > 1

Suppose the summation of a subarray from a(i) to a(j) is

#### T(i, j) = a(i) + a(i + 1) + ... + a(j - 1) + a(j), 1≤ i < j ≤ n.

It can be inferred that

#### 2.2 Define the multiple of k (k ≠ 0) by modulo

The problem is to find a continuous subarray of size at least 2 that sums up to the multiple of k, which means

#### T(i, j) = n × k, 1≤ i < j ≤ n.

That is to say

#### S(j) - S(i - 1) = n × k, 1 < i < j.

By doing the modulo, we get

## 3. Algorithm

#### 3.1. Special cases

A. The size of array < 2

• Since the size of subarray is at least 2, return false.

B. k = 0

#### T(i, j) = a(i) + a(i + 1) + ... + a(j - 1) + a(j) = 0.

As the array only contains non-negative numbers, that is to say

#### a(i) = a(i + 1) = ... = a(j - 1) = a(j) = 0.

Since the size of subarray is at least 2,

• if there are 2 adjacent zeros in the array, return true.

• If not, return false.

#### 3.2 Normal situation

Step 1: Summation

Do iteration by using the recursion formula

#### S(n) = a(n) + S(n - 1), n > 1.

Step 2: Modulo operation

There are 2 situations:

#### S(j) ≡ S(i - 1) mod k, 1 < i < j.

When doing iteration from j = 1 to j = n, we need to judge

A. When j > 1 and S(j) ≡ 0 mod k, return true.

B. Use a hash table (the key is S(i) mod k) to record THE FIRST i. If a same key appears twice (means S(j) ≡ S(i) mod k) and j - i > 1, return true.

(At first I didn't notice that the size is at least 2, thanks to @BavariaKing1822 )

C. After the iteration, return false.

## 4. Complexity analysis

#### 4.1 Time complexity

As Step 1 and Step 2 in Section 3 can be merged to a single iteration from j = 1 to j = n.

#### 4.2 Space complexity

As the hash table's key is a remainder from division based on integer k, the probable maximum size of the hash table is |k|.

## 5. Code

``````class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
if(nums.size() < 2) return false;
if(k == 0)
{
for(int i = 1; i < nums.size(); i++)
{
if(nums[i] == 0 && nums[i - 1] == 0) return true;
}
return false;
}else{
int i = 0;
map<int, int> res;
while(true)
{
if(i != 0 && nums[i] % k == 0)
{
return true;
}else{
if(res.find(nums[i] % k) == res.end())
{
res[nums[i] % k] = i;
}else{
if(i - res[nums[i] % k] > 1) return true;
}
}
i++;
if(i == nums.size()) return false;
nums[i] += nums[i - 1];
}
}
}
};
``````

• @KJer Can you try this test case

[2,13,4,5,1,13]
13

I think it is giving out different answer.

• @BavariaKing1822

Thank you for noticing me that the fact that the key appears twice only doesn't mean there are at least 2 elements between two indexes.

I use the hash table to record the first appeared index instead, and when the key appears twice, I will check the difference of two indexes.

The function will return true only when the difference is larger than 1.

• good~ clear and complete thinking process.
it help me a lot.

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.