Sponsored
Sponsored
This approach leverages prefix sums and the properties of modular arithmetic to efficiently count subarrays whose sums are divisible by k. By maintaining a hashmap (or dictionary) that keeps track of the frequency of each remainder observed when computing prefix sums modulo k, we can determine how many valid subarrays end at each position in the array.
For any position in the array, if we have the same remainder as a previously computed prefix sum, it indicates that the subarray between the two indices is divisible by k.
Time Complexity: O(n), where n is the number of elements in the array, as we iterate over the array once.
Space Complexity: O(k), where k is the number of different remainders we track in our modCount array.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int SubarraysDivByK(int[] nums, int k) {
6 Dictionary<int, int> modCount = new Dictionary<int, int>();
7 modCount[0] = 1;
8 int count = 0, cumSum = 0;
9 foreach (var num in nums) {
10 cumSum += num;
11 int mod = ((cumSum % k) + k) % k;
12 count += modCount.ContainsKey(mod) ? modCount[mod] : 0;
13 if (modCount.ContainsKey(mod)) {
modCount[mod]++;
} else {
modCount[mod] = 1;
}
}
return count;
}
public static void Main() {
Solution sol = new Solution();
int[] nums = new int[] {4, 5, 0, -2, -3, 1};
int k = 5;
Console.WriteLine("Number of subarrays divisible by " + k + ": " + sol.SubarraysDivByK(nums, k));
}
}This C# implementation uses a Dictionary to track frequencies of the remainders encountered when the cumulative sum is divided by k. The map is initialized with a zero frequency to account for subarrays starting at the beginning and those directly divisible by k. As each element is processed, the cumulative sum and remainder are updated; the frequency of subarrays is then increased based on past occurrences of the same remainder.
The brute force approach involves checking all possible subarrays to find those whose sum is divisible by k. This method is less efficient and should be used primarily for small inputs due to its higher time complexity. We iterate over all subarray starting points and compute the sum for all possible ending positions, counting subarrays that meet the criteria.
Time Complexity: O(n^2), where n is the number of elements in the array (due to double loop).
Space Complexity: O(1), as only integer counters and accumulators are used.
#include <vector>
int subarraysDivByK(std::vector<int>& nums, int k) {
int count = 0;
int n = nums.size();
for (int start = 0; start < n; start++) {
int sum = 0;
for (int end = start; end < n; end++) {
sum += nums[end];
if (sum % k == 0) {
count++;
}
}
}
return count;
}
int main() {
std::vector<int> nums = {4, 5, 0, -2, -3, 1};
int k = 5;
std::cout << "Number of subarrays divisible by " << k << ": " << subarraysDivByK(nums, k) << std::endl;
return 0;
}Implemented in C++, this approach iteratively evaluates each subarray by computing sums and checking divisibility by k. This brute force method involves a pair of nested loops, and directly sums elements between two indices to check if the total is divisible by k.