LeetCode 974: Subarray Sums Divisible by K Solution

Master LeetCode problem 974 (Subarray Sums Divisible by K), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

974. Subarray Sums Divisible by K

Medium

Array Hash Table Prefix Sum

Problem Explanation

Explanation

To solve this problem, we can use the concept of prefix sums. We iterate through the array and keep track of the running sum and the count of subarrays with a sum divisible by k. We can use a HashMap to store the count of different remainders when dividing the running sum by k. If at any point, we encounter a remainder that we have seen before, it means there is a subarray with a sum divisible by k. We increment the count by the number of times we have seen that remainder.

Algorithm:

Initialize a HashMap remainderCount with initial value (0, 1) to consider an empty subarray at the start.
Initialize variables runningSum and count to keep track of running sum and count of subarrays.
Iterate through the array and calculate the running sum.
Calculate the remainder of runningSum when divided by k.
If the remainder is negative, add k to make it positive.
If remainderCount contains the remainder, increment count by the value in remainderCount for that remainder.
Update the count of the current remainder in remainderCount.
Return the final count.

Time Complexity: O(n), where n is the length of the input array. Space Complexity: O(k), where k is the value of the input k.

Solution Code

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

        for (int num : nums) {
            runningSum += num;
            int remainder = runningSum % k;
            if (remainder < 0) {
                remainder += k;
            }
            if (remainderCount.containsKey(remainder)) {
                count += remainderCount.get(remainder);
            }
            remainderCount.put(remainder, remainderCount.getOrDefault(remainder, 0) + 1);
        }

        return count;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 974 (Subarray Sums Divisible by K)?

This page provides optimized solutions for LeetCode problem 974 (Subarray Sums Divisible by K) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 974 (Subarray Sums Divisible by K)?

The time complexity for LeetCode 974 (Subarray Sums Divisible by K) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 974 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 974 in Java, C++, or Python.

Back to LeetCode Solutions