_974. Subarray Sums Divisible by K.md

974. Subarray Sums Divisible by K

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 09, 2024

Last updated : July 01, 2024

---

Related Topics : Array, Hash Table, Prefix Sum

Acceptance Rate : 55.533 %

---

Solutions

• m974 Daily v1.py
• m974 Daily v2 Math REVISIT.py
• m974 Daily v2.java

Python

m974 Daily v1.py

# Weirdly slow hm --> ~5% runtime consistely

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        # prefix sum of remainders
        nums[0] %= k
        for i in range(1, len(nums)) :
            nums[i] = (nums[i] + nums[i - 1]) % k
        
        repeatRemainders = Counter(nums)
        output = repeatRemainders.get(0, 0)

        for key in repeatRemainders.keys() :
            if repeatRemainders.get(key) >= 2 :
                output += comb(repeatRemainders.get(key), 2)

        return output

m974 Daily v2 Math REVISIT.py

# I wanna redo this to understand the math

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        pastRemainders = {0: 1}
        runningRem = 0
        counter = 0
        for num in nums :
            runningRem = (runningRem + num) % k
            counter += pastRemainders.get(runningRem, 0)
            pastRemainders[runningRem] = pastRemainders.get(runningRem, 0) + 1
        return counter

Java

m974 Daily v2.java

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        HashMap<Integer, Integer> pastRemainders = new HashMap<>();
        pastRemainders.put(0, 1);

        int runningRemainder = 0;
        int outputCounter = 0;

        for (Integer num : nums) {
            runningRemainder = (runningRemainder + (num % k) + k) % k;
            outputCounter += pastRemainders.getOrDefault(runningRemainder, 0);
            pastRemainders.put(runningRemainder, pastRemainders.getOrDefault(runningRemainder, 0) + 1);
        }

        return outputCounter;
        
    }

    
}