We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Subarray Sums Divisible by K

Number: 1016

Difficulty: Medium

Paid? No

Companies: Uber, Amazon, Meta, TikTok, Citadel, Microsoft, Google, Apple, thoughtspot

Problem Description

Given an integer array and an integer k, count the number of non-empty contiguous subarrays whose sums are divisible by k.

Key Insights

  • Use the concept of prefix sums where prefix[i] represents the sum of elements from the start up to index i.
  • A subarray sum from index i+1 to j is divisible by k if and only if prefix[j] % k equals prefix[i] % k.
  • Use a hash table (or dictionary/map) to count occurrences of each remainder.
  • Initialize the hash table with the remainder 0 count set to 1 to account for subarrays that start from index 0.
  • Handle negative numbers by adjusting mod results to ensure they are non-negative.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the array, since we traverse the array once. Space Complexity: O(k) in the worst-case scenario, due to storing frequency counts of remainders.

Solution

We solve the problem using prefix sums and a hash table (or map) to track the frequency of each modulo value (prefix sum mod k). For each element in the array, we update the cumulative sum and compute its modulo with k. The number of valid subarrays ending at the current index is equal to the number of times this modulo value has been seen before (since the difference between two prefix sums with the same modulo is divisible by k). Finally, sum up these counts to obtain the answer.

Code Solutions

# Python Solution

def subarraysDivByK(nums, k):
    # Dictionary to store frequency of each remainder
    remainder_count = {0: 1}  # initialize with remainder 0 for subarrays starting at index 0
    current_sum = 0  # current prefix sum
    count = 0  # counter for valid subarrays
    
    # Iterate through the given array
    for num in nums:
        current_sum += num  # update the prefix sum
        # Compute the modulo while handling negative values
        remainder = current_sum % k
        
        # If this remainder has been seen before, add its count to our answer
        count += remainder_count.get(remainder, 0)
        
        # Update the frequency count for this remainder
        remainder_count[remainder] = remainder_count.get(remainder, 0) + 1
    
    return count

# Example Usage:
# print(subarraysDivByK([4,5,0,-2,-3,1], 5))
← Back to All Questions