# Question

Formatted question description: https://leetcode.ca/all/523.html

 523. Continuous Subarray Sum

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 a multiple of k,
that is, sums up to n*k where n is also an integer.

Example 1:

Input: [23, 2, 4, 6, 7],  k=6
Output: True
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.

Example 2:

Input: [23, 2, 6, 4, 7],  k=6
Output: True
Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.

Constraints:
The length of the array won't exceed 10,000.
You may assume the sum of all the numbers is in the range of a signed 32-bit integer.



# Algorithm

bruce force

note if k is 0 then mod will not work

# Code

• public class Continuous_Subarray_Sum {
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {

// input null check

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

return false;

}
}
}

############

class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
Map<Integer, Integer> mp = new HashMap<>();
mp.put(0, -1);
int s = 0;
for (int i = 0; i < nums.length; ++i) {
s += nums[i];
int r = s % k;
if (mp.containsKey(r) && i - mp.get(r) >= 2) {
return true;
}
if (!mp.containsKey(r)) {
mp.put(r, i);
}
}
return false;
}
}

• // OJ: https://leetcode.com/problems/continuous-subarray-sum
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
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 ((!k && !sum) || (k && sum % k == 0)) return true;
}
}
return false;
}
};

• class Solution:
def checkSubarraySum(self, nums: List[int], k: int) -> bool:
s = 0
mp = {0: -1}
for i, v in enumerate(nums):
s += v
r = s % k
if r in mp and i - mp[r] >= 2:
return True
if r not in mp:
mp[r] = i
return False

############

class Solution(object):
def checkSubarraySum(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
if k == 0:
return "0,0" in ",".join([str(n) for n in nums])
if len(nums) < 2:
return False
if len(nums) == 2:
return sum(nums) % k == 0
ppSum = 0
subSum = nums[0] + nums[1]
d = set([0])
for i in range(2, len(nums)):
ppSum = (ppSum + nums[i - 2]) % k
d |= {ppSum}
subSum = (subSum + nums[i]) % k
if subSum % k in d:
return True
return False


• func checkSubarraySum(nums []int, k int) bool {
mp := map[int]int{0: -1}
s := 0
for i, v := range nums {
s += v
r := s % k
if j, ok := mp[r]; ok && i-j >= 2 {
return true
}
if _, ok := mp[r]; !ok {
mp[r] = i
}
}
return false
}

• class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
int length = nums.length;
if (length < 2)
return false;
if (k == 0) {
for (int i = 1; i < length; i++) {
if (nums[i - 1] == 0 && nums[i] == 0)
return true;
}
return false;
}
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
map.put(0, -1);
int remainder = 0;
for (int i = 0; i < length; i++) {
remainder = (remainder + nums[i]) % k;
if (map.containsKey(remainder)) {
int prevIndex = map.get(remainder);
if (i - prevIndex > 1)
return true;
} else
map.put(remainder, i);
}
return false;
}
}

############

class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
Map<Integer, Integer> mp = new HashMap<>();
mp.put(0, -1);
int s = 0;
for (int i = 0; i < nums.length; ++i) {
s += nums[i];
int r = s % k;
if (mp.containsKey(r) && i - mp.get(r) >= 2) {
return true;
}
if (!mp.containsKey(r)) {
mp.put(r, i);
}
}
return false;
}
}

• // OJ: https://leetcode.com/problems/continuous-subarray-sum
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
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 ((!k && !sum) || (k && sum % k == 0)) return true;
}
}
return false;
}
};

• class Solution:
def checkSubarraySum(self, nums: List[int], k: int) -> bool:
s = 0
mp = {0: -1}
for i, v in enumerate(nums):
s += v
r = s % k
if r in mp and i - mp[r] >= 2:
return True
if r not in mp:
mp[r] = i
return False

############

class Solution(object):
def checkSubarraySum(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
if k == 0:
return "0,0" in ",".join([str(n) for n in nums])
if len(nums) < 2:
return False
if len(nums) == 2:
return sum(nums) % k == 0
ppSum = 0
subSum = nums[0] + nums[1]
d = set([0])
for i in range(2, len(nums)):
ppSum = (ppSum + nums[i - 2]) % k
d |= {ppSum}
subSum = (subSum + nums[i]) % k
if subSum % k in d:
return True
return False


• func checkSubarraySum(nums []int, k int) bool {
mp := map[int]int{0: -1}
s := 0
for i, v := range nums {
s += v
r := s % k
if j, ok := mp[r]; ok && i-j >= 2 {
return true
}
if _, ok := mp[r]; !ok {
mp[r] = i
}
}
return false
}