Vultr DocsLatest Content

Subarray Sums Divisible by K

Updated on 25 June, 2025
Subarray Sums Divisible by K header image

Problem Statement

The task is to count the number of contiguous subarrays within an integer array nums, where the sum of the elements in the subarray is divisible by a given integer k. The elements in the array, as well as the subarrays derived from it, can take on any integer value, positive or negative. Understanding that a "subarray" refers to a sequence of one or more elements that are contiguous segments of the main array, the solution should efficiently determine the count of such subarrays where the sum meets the divisibility criterion.

Examples

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

Approach and Intuition

The problem can be approached by focusing on the sum of subarrays and checking for divisibility by k. Here's the step-by-step plan:

  1. Utilize a Hash Map for Frequency Count of Remainders: As you iterate through the array, for each element, maintain a cumulative sum. For each new cumulative sum, compute the remainder of this sum when divided by k. Store and update the frequency of each unique remainder in a hash map.

  2. Understanding Remainder Behavior: The remainder, when divided by k, could potentially be negative (if the numbers in nums are negative and k is positive, for example). Volatility in remainder signs can be normalized by adjusting remainders: if a remainder is negative, simply add k to it to make it positive.

  3. Leverage the Pigeonhole and Prefix Sum Principle: The primary insight here leans on the idea of prefix sums. Specifically, if two prefix sums yield the same remainder upon division by k, then the elements lying between these two prefixes sum up to some multiple of k (hence, are divisible by k).

  4. Count Potential Subarrays: Every time a remainder repeats, it means there are multiple subarrays (ending at different indices) which have sums divisible by k. Use the hash map to count these occurrences. For each remainder, if it has been seen n times before, then there are n subarrays ending at the current index that can be formed which have sums divisible by k.

This approach capitalizes on both the properties of remainders and the utility of hash maps for efficient frequency counts, ensuring that each subarray is checked for divisibility without explicitly computing the sum for every possible subarray, thereby improving efficiency.

Solutions

  • C++
  • Java
cpp 
class Solution {
public:
    int subarraysWithSumDivisibleByK(vector<int>& array, int divisor) {
        int length = array.size();
        int currentMod = 0, totalCount = 0;

        vector<int> remainderCount(divisor);
        remainderCount[0] = 1;

        for (int element : array) {
            currentMod = (currentMod + element % divisor + divisor) % divisor;
            totalCount += remainderCount[currentMod];
            remainderCount[currentMod]++;
        }

        return totalCount;
    }
};

The provided C++ code defines a solution for finding the count of subarrays within an integer array where the sum of the elements is divisible by a given divisor K. The function subarraysWithSumDivisibleByK accepts two parameters: a vector array and an integer divisor. It utilizes the properties of modulo operation to efficiently compute the number of such subarrays.

Here's how the function works:

  1. Initialize length to hold the size of the input array.

  2. Initialize currentMod to store the current prefix sum modulus and totalCount to track the total number of valid subarrays.

  3. Create a vector remainderCount of size divisor to store the frequency of each modulus value in prefix sums, with an initial count of one for the 0 modulus to account for sums that are exactly divisible by divisor.

  4. Loop over each element of the array:

    • Update currentMod by adding the current element's modulus value, adjusted for negative sums by adding divisor and taking the modulus again.
    • Increment totalCount by the count of previous prefix sums that share the same modulus as currentMod, which means their difference is divisible by divisor.
    • Increment the count of the current modulus in remainderCount.

The function ultimately returns totalCount, which represents the number of subarrays where the sum is divisible by divisor. This approach ensures a comprehensive check through the use of modular arithmetic, optimizing the process to find qualifying subarrays efficiently using a time complexity dependent on the size of the array and the divisor.

java 
class Solution {
    public int countSubarraysDivisibleByK(int[] array, int divisor) {
        int length = array.length;
        int cumulativeModulo = 0, totalCount = 0;

        int[] remainderGroups = new int[divisor];
        remainderGroups[0] = 1;

        for (int value : array) {
            cumulativeModulo = (cumulativeModulo + value % divisor + divisor) % divisor;
            totalCount += remainderGroups[cumulativeModulo];
            remainderGroups[cumulativeModulo]++;
        }

        return totalCount;
    }
}

This Java solution tackles the problem of counting the number of subarrays from a given array where the sum of elements is divisible by a specified value, K. The approach utilizes a cumulative sum and the modulo operation to efficiently compute the result.

Here's a step-by-step explanation of how the solution works:

  1. Initialize length to the size of the input array for easy reference.

  2. Declare cumulativeModulo to store the ongoing sum of array values modulo divisor. Start with totalCount to count the number of subarrays meeting the criteria.

  3. Create an array remainderGroups to track how many times each modulo value has occurred so far with a size equal to divisor. Initialize the first element to 1 to account for the subarray consisting of the very first element if it is divisible by divisor.

  4. Iterate through each element in the input array:

    • Update cumulativeModulo by adding the current value modulo divisor and adjust for any negative values to ensure all remainders are positive.
    • Increase totalCount by the count of subarrays that have the same cumulativeModulo value recorded in remainderGroups. This is because if two subarrays have the same remainder when divided by divisor, the subarray between them has a sum that is divisible by divisor.
    • Increment the count for the current cumulativeModulo in remainderGroups.

  5. Return the total count of divisible subarrays.

The solution leverages the properties of the modulo operation and prefix sums to elegantly solve a potentially complex problem using a linear time algorithm that is both efficient and easy to understand.

Comments

No comments yet.