Is Subarray Sums Divisible by K easy or hard?

The problem is classified as Medium because the brute force idea is straightforward but the optimal solution requires recognizing the prefix sum remainder pattern. Understanding how equal remainders imply divisible subarrays is the key insight.

Subarray Sums Divisible by K Python/Java solution

Both Python and Java implementations use the same prefix sum + hash map technique. Track the running sum, compute remainder = (sum % k + k) % k, add the existing frequency of that remainder to the result, and update the map. The algorithm runs in O(n) time with O(k) space.

How to solve Subarray Sums Divisible by K in O(n)?

Maintain a running prefix sum and compute its remainder modulo k at each step. Store how many times each remainder has appeared in a hash map. If the same remainder occurs again, add its frequency to the result because those earlier prefix sums form subarrays whose sums are divisible by k.

What is the best approach for Subarray Sums Divisible by K?

The optimal approach uses prefix sums with a hash map that stores frequencies of remainders when prefix sums are divided by k. If the same remainder appears twice, the subarray between those indices has a sum divisible by k. This method runs in O(n) time and O(k) space, making it efficient for large inputs.

Is Subarray Sums Divisible by K asked at Google/Amazon/Meta?

This problem is a common prefix sum and hashing pattern frequently discussed in coding interviews at large tech companies such as Amazon, Google, and Meta. Variants involving prefix sums, modulo arithmetic, and subarray counting appear regularly in interview question banks.

What data structure is used in Subarray Sums Divisible by K?

The optimal solution uses a hash map (or dictionary) to store frequencies of prefix sum remainders. Combined with a running prefix sum over the array, the hash table enables constant-time lookup to count valid subarrays.

What is the time complexity of Subarray Sums Divisible by K?

The optimal solution runs in O(n) time because the array is processed once while maintaining a hash map of remainder counts. The brute force approach requires checking every subarray, which leads to O(n²) time complexity.

Description Solution Video 16:41

974. Subarray Sums Divisible by K

Medium56.7% acceptance11 companies

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.

Example 1:

Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by k = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

Example 2: