Subarray Sums Divisible by K

Two prefix sums have a difference divisible by k when they leave the same remainder modulo k. Maintain remainder = (remainder + value) % k as you scan, normalize it with (remainder + k) % k when negatives are possible, and keep a map from remainder to how often it has appeared. Initialize remainder zero with count one because a prefix itself divisible by k is valid. At each position, add the prior count for the current remainder to the answer, then increment that count. Each earlier equal remainder forms one subarray ending at the current index. This is O(n) expected time and O(min(n,k)) space. If k is positive and modest, an array of size k is faster than a map; clarify how a zero or negative divisor should be treated because modulo by zero is undefined and most versions require positive k.