Dare2Solve
The problem involves finding a subarray of at least two elements whose sum is a multiple of a given integer ( k ). A key observation is that if the cumulative sum up to two different indices has the same remainder when divided by ( k ), then the sum of the elements between these two indices is a multiple of ( k ). This is because the difference between two sums with the same remainder is divisible by ( k ).
class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
unordered_map<int, int> map = {{0, -1}};
int sum = 0;
for (int i = 0; i < nums.size(); i++) {
sum += nums[i];
int rem = sum % k;
if (map.find(rem) != map.end()) {
if (i - map[rem] >= 2) {
return true;
}
} else {
map[rem] = i;
}
}
return false;
}
};
class Solution:
def checkSubarraySum(self, nums: List[int], k: int) -> bool:
prefix_sum = {0: -1}
total = 0
for i, num in enumerate(nums):
total += num
remainder = total % k
if remainder in prefix_sum:
if i - prefix_sum[remainder] >= 2:
return True
else:
prefix_sum[remainder] = i
return False
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
map.put(0, -1);
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
int rem = sum % k;
if (map.containsKey(rem)) {
if (i - map.get(rem) >= 2) {
return true;
}
} else {
map.put(rem, i);
}
}
return false;
}
}
/**
* @param {number[]} nums
* @param {number} k
* @return {boolean}
*/
var checkSubarraySum = function (nums, k) {
let map = new Map([[0, -1]]);
let sum = 0;
for (let i = 0; i < nums.length; i++) {
sum += nums[i];
let rem = sum % k;
if (map.has(rem)) {
if (i - map.get(rem) >= 2) {
return true;
}
}
else {
map.set(rem, i);
}
}
return false;
};