Space | teamleaderleo

974. Subarray Sums Divisible by K

This problem is very similar to Subarray Sum Equals K, but instead of looking for a specific sum, we are looking for remainders. If the prefix sum up to index i and index j have the same remainder when divided by K, then the subarray between them must be divisible by K.

The Logic:

Prefix Sum with Modulo: As we iterate through the array, maintain a running prefix_sum. Calculate the remainder: remainder = prefix_sum % K.
Handle Negative Remainders: In many programming languages, -1 % 5 results in -1. To ensure we map this correctly, use (prefix_sum % K + K) % K to always get a positive remainder.
Hash Map (Frequency Table): Use a map (or an array of size K) to store how many times each remainder has occurred.
Counting: If a remainder has appeared times before, it means there are n new subarrays ending at the current index that are divisible by K.

class Solution:
    from collections import defaultdict
    def subarraysDivByK(self, nums: list[int], k: int) -> int:
        # count stores the frequency of remainders encountered so far
        # Initialize with {0: 1} to handle subarrays that are divisible 
        # from the very beginning (index 0).
        remainder_freq = {0: 1}
        
        current_sum = 0
        count = 0
        
        for num in nums:
            current_sum += num
            
            # Calculate remainder. Python's % operator handles negative 
            # numbers correctly for this specific logic (e.g., -1 % 5 = 4).
            remainder = current_sum % k
            
            # If we have seen this remainder before, it means there are 
            # subarrays ending here that are divisible by k.
            if remainder in remainder_freq:
                count += remainder_freq[remainder]
                remainder_freq[remainder] += 1
            else:
                remainder_freq[remainder] = 1
                
        return count

← → or j/k to navigate · Space to hide content