Scale Engineer

Subarray Sums Divisible by K

Med
#0928Time: 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: O(1), as we only use a constant amount of extra space for variables like `count` and `currentSum`.4 companies
Patterns
Prefix Sum
Data structures
ArrayHash Table
Companies
ExpediaTinkoffCitadelthoughtspot

Prompt

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 * 104
  • -104 <= nums[i] <= 104
  • 2 <= k <= 104

Approaches

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

O(1), as we only use a constant amount of extra space for variables like `count` and `currentSum`.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem