• Posts

Problem 974 Subarray Sums Divisible by K

Problem Statement

Link - Problem 974

Question

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

Solution

/*class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        std::ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);

        vector<int> prefixSum(nums.size(),0);
        prefixSum[0] =nums[0];
        for(int i = 1; i<nums.size(); i++)
            prefixSum[i] = prefixSum[i-1]+nums[i];
        int ans = 0;
        int temp;
        for(int i = 0;i<nums.size();i++)
        {
            for(int j = i; j<nums.size();j++)
            {
                temp = i==0?0:prefixSum[i-1];
                if((prefixSum[j]-temp)%k == 0)
                    ans++;
            }
        }
        return ans;
    }
};*/


class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        std::ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);

        unordered_map<int, int> map;
        map[0] = 1;
        int currsum = 0;
        int ans = 0;
        for(int i = 0; i < nums.size(); i++) {
            currsum += nums[i];
            int remainder = currsum % k;
            if(remainder < 0)
                remainder += k;
            ans += map[remainder];
            map[remainder]++;
        }
        return ans;
    }
};

Complexity Analysis

| Algorithm               | Time Complexity | Space Complexity |
| ----------------------- | --------------- | ---------------- |
| Prefix Sum with Hashmap | O(n)            | O(k)             |

Explanation

Intial Thoughts

The problem can be approached by considering all possible subarrays, calculating their sum, and checking if the sum is divisible by k. Another thought is to use prefix sums to efficiently calculate the sum of any subarray. We also need to think about how to efficiently store and look up the remainders when dividing by k. Key points to consider are: the use of prefix sums, iterating over all possible subarrays, and efficiently checking divisibility by k. Additionally, we should consider how to handle negative numbers and how to avoid counting empty subarrays. We also need to think about time complexity and how to optimize it.

Intuitive Analysis

To intuitively solve this problem, we can think of it as finding patterns in the data that allow us to quickly identify subarrays with sums divisible by k. We can use a hashmap to store the frequency of each remainder when dividing the sum by k. Key points to consider are: the hashmap can help us to avoid counting the same subarray multiple times, we should iterate over the array and for each element, calculate its contribution to the current sum, and then update the hashmap accordingly. We should also consider how to correctly handle the case when the remainder is negative. Furthermore, we should think about how to initialize the hashmap and how to return the correct count of subarrays with sums divisible by k. Additionally, we should analyze the time complexity of our approach and consider any potential optimizations.

1. Intuition

• The problem requires finding the number of non-empty subarrays with a sum divisible by k
• To solve this, we can utilize the concept of prefix sums to efficiently calculate the sum of subarrays
• However, calculating all possible subarrays and checking their sums would result in a time complexity of O(n^2), which is inefficient
• A key insight is to use the property that if the sum of a subarray is divisible by k, then the remainder of the sum when divided by k is 0
• We can use a hashmap to store the frequency of remainders when dividing the prefix sum by k
• This approach allows us to count the number of subarrays with a sum divisible by k in linear time complexity
• The solution works by iterating through the array and updating the prefix sum and remainder, then using the hashmap to count the subarrays

2. Implementation

• We initialize an unordered_map called map to store the frequency of remainders, with map[0] = 1 to handle the case where the sum of the subarray is 0
• We iterate through the array, updating the currsum variable with the current prefix sum using currsum += nums[i]
• We calculate the remainder of the current prefix sum when divided by k using int remainder = currsum % k
• If the remainder is negative, we add k to it to ensure it falls within the range [0, k-1] using if(remainder < 0) remainder += k
• We increment the count of subarrays with a sum divisible by k using ans += map[remainder]
• We update the frequency of the current remainder in the hashmap using map[remainder]++
• Finally, we return the total count of subarrays with a sum divisible by k using return ans

Complexity Analysis

Time Complexity:

• The provided code has two approaches, the first one has a time complexity of O(n^2) due to the nested loops for(int i = 0;i<nums.size();i++) and for(int j = i; j<nums.size();j++). However, the optimized approach using an unordered_map has a time complexity of O(n), where n is the number of elements in the input array nums, because it only requires a single pass through the array.
• The dominant operation in this optimized approach is the iteration over the array nums and the hashmap operations, which take constant time on average. The expression currsum += nums[i] and int remainder = currsum % k also take constant time, contributing to the overall linear time complexity.
• The justification of the Big O classification of O(n) comes from the fact that the number of operations performed grows linearly with the size of the input array nums. This is evident from the single loop for(int i = 0; i < nums.size(); i++) that iterates over each element in nums exactly once.

Space Complexity:

• The memory usage of the optimized approach is primarily due to the unordered_map map used to store the remainders of the prefix sums. The maximum number of elements stored in the map is equal to the number of possible remainders when dividing by k, which is k. Therefore, the space complexity is O(k).
• The impact of the data structure on space complexity is significant because the map can store up to k elements in the worst-case scenario. However, the space used does not grow with the size of the input array nums, but rather with the value of k.
• The justification of the space complexity comes from the fact that the maximum amount of extra space used by the algorithm does not depend on the size of the input array nums, but rather on the value of k, which is a constant factor in the context of the problem.

Footnote

This question is rated as Medium difficulty.

Similar Questions: