Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

1016. Subarray Sums Divisible by K

My accepted Python solution to LeetCode problem 1016, Subarray Sums Divisible by K, running in 26ms.

  • Difficulty: Medium
  • Python
  • Runtime 26ms
  • Memory 21.2MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 26ms, memory 21.2MB, accepted 2026-01-02.

python
class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        # Use prefix sum and count remainders
        count = {0: 1}  # remainder -> count of prefix sums with this remainder
        prefix_sum = 0
        result = 0
        
        for num in nums:
            prefix_sum += num
            remainder = prefix_sum % k
            
            # If we've seen this remainder before, those prefix sums
            # form subarrays with sum divisible by k
            if remainder in count:
                result += count[remainder]
            
            count[remainder] = count.get(remainder, 0) + 1
        
        return result

Source