Took me a minute to stop thinking brute force.
Use prefix sums modulo k and a hash map to track the earliest index of each remainder. If a remainder repeats at indices i and j (i < j), the subarray between them has a sum divisible by k; ensure the subarray length is at least 2 by checking j - i >= 2.
Pro tip: Clarify edge cases upfront: k can be negative or zero (though typically k > 0), and the array may contain negative numbers. Mention that the modulo operation should handle negatives correctly (e.g., using ((sum % k) + k) % k).
Restate the problem: find a contiguous subarray of length >= 2 whose sum is divisible by k. Confirm constraints and edge cases (e.g., k=0, negative numbers).
Compute prefix sums modulo k. If two prefix sums have the same remainder, the subarray between them has a sum divisible by k.
Use a hash map to store the first index where each remainder occurs. Initialize with remainder 0 at index -1 to handle subarrays starting from the beginning.
When a remainder repeats, check if the distance between indices is at least 2. If yes, return true. Otherwise, continue.
If no valid subarray found, return false. Time complexity O(n), space O(min(n, k)).
AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.