Leetcode Problem

[HarnoorMalik]

Discussion Type

Product Feedback

Discussion Content

I'm stuck with the following problem:

Count subarrays with sum divisible by k.

Given an integer array nums and an integer k (k ≠ 0), return the number of non-empty contiguous subarrays whose sum is divisible by k.

Example

nums = [4, 5, 0, -2, -3, 1], k = 5 → 7
The qualifying subarrays are: [4,1], [5], [5,0], [5,0,-2,-3], [0], [0,-2,-3], [-2,-3].

Constraints

1 ≤ len(nums) ≤ 2e5

-1e9 ≤ nums[i] ≤ 1e9

-1e9 ≤ k ≤ 1e9, k ≠ 0

[aryankumawat]

This should answer your problem:

from collections import defaultdict

def subarrays_div_by_k(nums, k):
count_by_rem = defaultdict(int)
count_by_rem[0] = 1

total = 0
pref = 0
for x in nums:
    pref += x
    rem = (pref % k + k) % k  # normalize for negatives
    total += count_by_rem[rem]
    count_by_rem[rem] += 1

return total

test this with:

print(subarrays_div_by_k([4, 5, 0, -2, -3, 1], 5)) # 7

[mecodeatlas]

Thanks for posting in the GitHub Community, @HarnoorMalik!

We're happy you're here. You are more likely to get a useful response if you are posting your question in the applicable category, the Discussions category is solely related to conversations around the GitHub product Discussions. This question should be in the Programming Help category. I've gone ahead and moved it for you. Good luck!

[saimkhan772]

from collections import defaultdict

def count_subarrays_divisible_by_k(arr, k):
remainder_count = defaultdict(int)
remainder_count[0] = 1 # base case: prefix sum itself divisible by k

prefix_sum = 0
subarray_count = 0

for num in arr:
    prefix_sum += num
    remainder = prefix_sum % k
    
    # handle negative remainder normalization
    if remainder < 0:
        remainder += k
    
    # add number of previous prefix sums with same remainder
    subarray_count += remainder_count[remainder]
    
    # record this remainder for future matches
    remainder_count[remainder] += 1

return subarray_count