Subarray Sums Divisible by K

MEDIUM

Description

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:

Input: nums = [5], k = 9
Output: 0

Constraints:

1 <= nums.length <= 3 * 10⁴
-10⁴ <= nums[i] <= 10⁴
2 <= k <= 10⁴

Approaches

Checkout 2 different approaches to solve Subarray Sums Divisible by K. Click on different approaches to view the approach and algorithm in detail.

Brute Force Approach

The most straightforward approach is to generate every possible contiguous subarray, calculate the sum of its elements, and then check if that sum is divisible by k. If it is, we increment a counter. This method is easy to conceptualize but computationally expensive.

Algorithm

Initialize a counter count to 0.
Use a nested loop structure to iterate through all possible subarrays.
- The outer loop with index i determines the start of the subarray.
- The inner loop with index j determines the end of the subarray.
For each subarray defined by i and j, calculate its sum.
- Initialize a currentSum to 0 before the inner loop.
- In the inner loop, accumulate the sum by adding nums[j] to currentSum.
Check if the currentSum is divisible by k (i.e., currentSum % k == 0).
If the condition is met, increment the count.
After all subarrays have been checked, return the final count.

This approach uses two nested loops to define the boundaries of each subarray. The outer loop iterates from the first element to the last, fixing the starting point of the subarray. The inner loop then iterates from this starting point to the end of the array, defining the ending point. For each subarray generated, we maintain a running sum. After adding each new element to the subarray, we check if the current running sum is divisible by k. We keep a total count of all such subarrays found.

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            int currentSum = 0;
            for (int j = i; j < nums.length; j++) {
                currentSum += nums[j];
                if (currentSum % k == 0) {
                    count++;
                }
            }
        }
        return count;
    }
}

Complexity Analysis

Time Complexity: O(N^2), where N is the number of elements in the `nums` array. The two nested loops lead to a quadratic number of operations as we calculate the sum for each of the N*(N+1)/2 subarrays.Space Complexity: O(1), as we only use a constant amount of extra space for variables like `count` and `currentSum`.

Pros and Cons

Pros:

Simple to understand and implement.
Requires no extra space other than a few variables.

Cons:

Highly inefficient for larger arrays.
Will likely result in a 'Time Limit Exceeded' (TLE) error on most online judges for the given constraints.

Code Solutions

Checking out 3 solutions in different languages for Subarray Sums Divisible by K. Click on different languages to view the code.

class Solution {
public
  int subarraysDivByK(int[] nums, int k) {
    Map<Integer, Integer> cnt = new HashMap<>();
    cnt.put(0, 1);
    int ans = 0, s = 0;
    for (int x : nums) {
      s = ((s + x) % k + k) % k;
      ans += cnt.getOrDefault(s, 0);
      cnt.merge(s, 1, Integer : : sum);
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Subarray Sums Divisible by K

Patterns:

Prefix Sum

Data Structures:

ArrayHash Table

Companies:

Expedia |Tinkoff |Citadel |thoughtspot |