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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Subarray Sums Divisible by K

Difficulty: Medium

Problem Description

Given an integer array nums and an integer k, return the number of non-empty subarrays that have a sum divisible by k. A subarray is a contiguous part of an array.

Key Insights

  • The problem involves finding subarrays whose sum is divisible by a given integer k.
  • Using the prefix sum technique can simplify the calculation of subarray sums.
  • To efficiently track the counts of prefix sums that give the same remainder when divided by k, a hash map (or dictionary) can be utilized.
  • The total number of valid subarrays can be derived from the frequency of the same remainders.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(k)

Solution

To solve the problem, we can use the prefix sum approach along with a hash map to keep track of how many times each remainder has appeared. The key steps are as follows:

  1. Initialize a hash map to store the count of each remainder when the prefix sum is divided by k.
  2. Iterate through the array while maintaining a running sum (prefix sum).
  3. For each element, calculate the current prefix sum and its remainder when divided by k.
  4. If the remainder is negative, adjust it to ensure it falls within the range of [0, k-1].
  5. Check if this remainder has been seen before in the hash map; if so, it means there are subarrays that sum to a value divisible by k.
  6. Update the hash map with the current remainder.

This approach allows us to count the valid subarrays in a single pass through the array.

Code Solutions

def subarraysDivByK(nums, k):
    count = 0
    prefix_sum = 0
    remainder_count = {0: 1}  # Start with remainder 0

    for num in nums:
        prefix_sum += num
        remainder = prefix_sum % k
        # Adjust for negative remainders
        if remainder < 0:
            remainder += k
        
        # If this remainder has been seen before, add the count of how many times it has been seen
        if remainder in remainder_count:
            count += remainder_count[remainder]
        
        # Update the count of this remainder
        remainder_count[remainder] = remainder_count.get(remainder, 0) + 1

    return count
← Back to All Questions