# Need to pay attention to a lot of corner cases...

• This problem contributed a lot of bugs to my contest score... Let's read the description again, pay attention to `red` sections:

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`.

Some `damn it!` test cases:

1. [0], 0 -> false;
2. [5, 2, 4], 5 -> false;
3. [0, 0], 100 -> true;
4. [1,5], -6 -> true;
etc...
``````public class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
// Since the size of subarray is at least 2.
if (nums.length <= 1) return false;
// Two continuous "0" will form a subarray which has sum = 0. 0 * k == 0 will always be true.
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] == 0 && nums[i + 1] == 0) return true;
}

// At this point, k can't be "0" any longer.
if (k == 0) return false;
// Let's only check positive k. Because if there is a n makes n * k = sum, it is always true -n * -k = sum.
if (k < 0) k = -k;

Map<Integer, Integer> sumToIndex = new HashMap<>();
int sum = 0;
sumToIndex.put(0, -1);

for (int i = 0; i < nums.length; i++) {
sum += nums[i];
// Validate from the biggest possible n * k to k
for (int j = (sum / k) * k; j >= k; j -= k) {
if (sumToIndex.containsKey(sum - j) && (i - sumToIndex.get(sum - j) > 1)) return true;
}
if (!sumToIndex.containsKey(sum)) sumToIndex.put(sum, i);
}

return false;
}
}
``````

• I got 11 bugs... Just blown my mind. Next time I gotta read the description more carefully...

• No doubt the edge cases were the trickiest part of this problem. I did not expect to see k being zero or negative or that a factor would be times zero. Anyhow, you definitely end up with a few more if statements!

``````    public bool CheckSubarraySum(int[] nums, int k)
{
Dictionary<int,int> map = new Dictionary<int,int>();
map[0] = -1;
int sum = 0;
for (int i = 0; i < nums.Length; i++)
{
sum += nums[i];
if (sum == 0 && i >= 1) return true;
if (k != 0)
{
int mod = sum % k;
if (map.ContainsKey(mod))
{
if (i - map[mod] >= 2) return true;
}
else
{
map[mod] = i;
}
}

}

return false;
}
``````

• Similar solution with you (submitted in contest) in c++

``````class Solution {
public:

bool hasZero(vector<int>& nums){
for(int i=1; i<nums.size(); i++){
if(nums[i] == 0 && nums[i-1] == 0) return true;
}
return false;
}

bool checkSubarraySum(vector<int>& nums, int k) {
if(nums.size() < 2) return false;
else if(hasZero(nums)) return true;

if(k == 0) return false;
k = abs(k);
if(k == 1) return true;

for(int i=0; i<nums.size(); i++){
int sum = nums[i];
for(int j=i+1; j<nums.size(); j++){
sum += nums[j];
if(sum % k == 0) return true;
}
}
return false;
}
};
``````

• A concise version in python

``````    def checkSubarraySum(self, nums, k):
cache = {}
cur = 0
for i, x in enumerate(nums):
if cur not in cache: cache[cur] = i
cur = (cur + x) % k if k != 0 else cur + x
if cur in cache and i > cache[cur]: return True
return False
``````

PS: Got 11 bugs for modifying it, I want my acceptance rate back T_T

• Good solution, But can it handle the cases: [1,2] 2 ?

• This post is deleted!

• @wangv
I don't think it does. It doesn't handle the length of the subarray.

• It's good solution. But it doesn't handle the length of the subarray.
I think we should use Map instead of Set to keep track of the ending index of the sum so that we could check for the length.

• [1, 1, -2], 0 ; should return true, but this function will return false?

• concise c++ using map

``````class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
//find accumulative sums
vector<int>sums{0};
unordered_map<int, vector<int>> map;
map[0].push_back(-1);
for(int i = 0; i < nums.size(); i++){
int residue = (k == 0)? sums.back() + nums[i] : (sums.back() + nums[i]) % k;
sums.push_back(residue);
map[residue].push_back(i); //vector should be always sorted!
if(i - map[residue][0] >= 2) return true;
}
return false;
}
};
``````

• Handling Corner Cases
Check in Array

1. has_zero
2. Two_consecutive Zero

**If Array has Zero and K is 0, then check if it has two_zero if its has two_zero return True.
else False.

If Array don't have zero but k==0
return false.**

Rest the Problem is Piece of a Cake Use the Idea of Range Sum Query problem.

``````class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {

int n=nums.size();
if(n<2)
return false;
bool has_zero=false;
bool two_zero=false;
// Handling Corner Case
for(int i=0;i<n;i++)
{
if(nums[i]==0)
{
has_zero=true;
break;
}
}

for(int i=0;i<n-1;i++)
{
if(nums[i]==0 && nums[i+1]==0)
{
two_zero=true;
break;
}
}

if(has_zero && k==0)
{
if(two_zero==true)
return true;
return false;
}
if(k==0 && has_zero==false)
return false;

//

int dp[n+1];
dp[0]=0;
for(int i=1;i<=n;i++)
{
dp[i]=nums[i-1]+dp[i-1];
}

int i=n,j=0;
while(i>0)
{
for(j=0;j<i-1;j++)
{
if((dp[i]-dp[j])%k==0)
return true;
}
i--;
}
return false;

}
};
``````

• @shawngao This code gets accepted, but is incorrect for test case "[1, 2] 2"

• @zestypanda You are right. Fixed my solution, thanks!

• I just want to provide my understanding to this solution:
We compute the sum for `0` to `i`. And we know that a sum of subarray is a sum of `0~i` subtract a sum of `0~j`.
If we know the remainder(`sum % k`) of this two sum, that mains these two sums are `n * k + remainder`, and we remove the `n * k` part from these two sum because we don't care what is the `n`. If these two sum have same remainder, we can Eliminate the remainder, and the sum of subarray should be some `n * k`.

• Thanks .
`for (int j = (sum / k) * k; j >= k; j -= k) {`
this part solved my problem. I have a similar method, but try to traverse from small to big, then got TLE for testcase [1,1000000000]

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