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.
1import java.util.HashMap;
2
3public class Solution {
4 public int subarraysDivByK(int[] nums, int k) {
5 HashMap<Integer, Integer> modCount = new HashMap<>();
6 modCount.put(0, 1);
7 int count = 0, cumSum = 0;
8 for (int num : nums) {
9 cumSum += num;
10 int mod = ((cumSum % k) + k) % k;
11 count += modCount.getOrDefault(mod, 0);
12 modCount.put(mod, modCount.getOrDefault(mod, 0) + 1);
13 }
14 return count;
15 }
16
17 public static void main(String[] args) {
18 Solution sol = new Solution();
19 int[] nums = {4, 5, 0, -2, -3, 1};
20 int k = 5;
21 System.out.println("Number of subarrays divisible by " + k + ": " + sol.subarraysDivByK(nums, k));
22 }
23}This Java solution uses a HashMap to maintain the frequency of each remainder seen when calculating the cumulative sum modulo k. The remainder 0 is initialized to 1 in the map, allowing for direct counting of subarrays with a sum that is initially divisible by k. The iteration through the array updates the cumulative sum, computes its remainder and increments the count of all subarrays by the number of times the remainder has been seen.
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.
This C implementation follows a nested loop technique. The first loop sets potential starting points for subarrays, and the inner loop accumulates sums for subarrays ending at each subsequent index. Each valid subarray whose sum is zero modulo k is counted. This approach is simple but becomes inefficient as input sizes grow.