Continuous Subarray Sum (Multiple of K)

Problem

Given an array of integers and an integer k, determine if the array has a contiguous subarray of size at least 2 whose sum is a multiple of k.

Input:  nums = [23,2,4,6,7], k = 6
Output: true   ([2,4] sums to 6)

Python Solution

def check_subarray_sum(nums, k):
    remainder_index = {0: -1}
    prefix_sum = 0
    for i, num in enumerate(nums):
        prefix_sum += num
        remainder = prefix_sum % k if k != 0 else prefix_sum
        if remainder in remainder_index:
            if i - remainder_index[remainder] > 1:
                return True
        else:
            remainder_index[remainder] = i
    return False

C++ Solution

bool checkSubarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> remainderIndex;
    remainderIndex[0] = -1;
    long prefixSum = 0;
    for (int i = 0; i < nums.size(); i++) {
        prefixSum += nums[i];
        int remainder = k == 0 ? prefixSum : prefixSum % k;
        if (remainderIndex.count(remainder)) {
            if (i - remainderIndex[remainder] > 1) return true;
        } else {
            remainderIndex[remainder] = i;
        }
    }
    return false;
}

Java Solution

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

Complexity

Time: O(n) — one pass, with O(1) average hash map lookups. Space: O(min(n, k)) — at most k distinct remainders can exist, bounded also by n.