aboutsummaryrefslogtreecommitdiff
path: root/subarr_sum_divisible_k.cpp
blob: 3661c96db8e601369a79d72c44d1423305b9bee2 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 974. Subarray Sums Divisible by K
#include "leetcode.h"
#include <vector>

/*
 * given: integer array 'nums' and integer 'k'
 * return: number of non-empty subarrays that
 * have a sum divisible by 'k'.
 * a subarray is a contiguous part of an array
 */

class Solution {
public:
  int subarraysDivByK(vector<int> &nums, int k) {
    vector<int> count(k);
    count[0] = 1;
    int prefix = 0, ans = 0;
    for (int i : nums) {
      prefix = (prefix + i % k + k) % k;
      ans += count[prefix]++;
    }
    return ans;
  }
};

int main() {
  Solution obj;
  vector<int> nums1 = {4, 5, 0, -2, -3, 1}, nums2 = {5};
  cout << obj.subarraysDivByK(nums1, 5); // expect: 7
  cout << obj.subarraysDivByK(nums2, 9); // expect: 0
  return 0;
}