k.
Problem
You are given an integer arraynums and an integer k.
Return
true if there exists a contiguous subarray containing at least two elements whose sum is a multiple of k. Otherwise, return false.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
nums = [23,2,4,6,7]
k = 6Solution
This problem can be solved using Prefix Sum and a HashMap. As we traverse the array, we maintain a running sum and calculate its remainder when divided byk.
If two prefix sums have the same remainder, their difference is divisible by
k. Therefore, the elements between those two positions have a sum that is a multiple of k.
We store the earliest index at which each remainder occurs. If the same remainder appears again, we check whether the distance between the two indices is at least
2, because the subarray must contain at least two elements.
We initially store remainder
0 at index -1. This handles valid subarrays that start from index 0.
We store only the first occurrence of each remainder because an earlier index gives us the longest possible subarray for that remainder.
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
// Track the earliest index where each remainder occurs.
Map<Integer, Integer> remainderToIndexMap = new HashMap<>();
// Handles valid subarrays that start from index 0.
remainderToIndexMap.put(0, -1);
int runningSum = 0;
for (int i = 0; i < nums.length; i++) {
runningSum += nums[i];
int remainder = runningSum % k;
if (remainderToIndexMap.containsKey(remainder)) {
// At least two elements must be present.
if (i - remainderToIndexMap.get(remainder) >= 2) {
return true;
}
} else {
// Store only the first occurrence.
remainderToIndexMap.put(remainder, i);
}
}
return false;
}
}
Complexity
Each element is processed once, and HashMap operations takeO(1) average time, resulting in O(n) time complexity.
The HashMap stores the first occurrence of each remainder and requires
O(min(n, k)) space.