Skip to content

974. Subarray Sums Divisible by K 👍

  • Time:
  • Space:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
 public:
  int subarraysDivByK(vector<int>& A, int K) {
    int ans = 0;
    int prefix = 0;
    vector<int> count(K);
    count[0] = 1;

    for (int a : A) {
      prefix = (prefix + a % K + K) % K;
      ans += count[prefix];
      ++count[prefix];
    }

    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
  public int subarraysDivByK(int[] A, int K) {
    int ans = 0;
    int prefix = 0;
    int[] count = new int[K];
    count[0] = 1;

    for (int a : A) {
      prefix = (prefix + a % K + K) % K;
      ans += count[prefix];
      ++count[prefix];
    }

    return ans;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def subarraysDivByK(self, A: List[int], K: int) -> int:
    ans = 0
    prefix = 0
    count = [1] + [0] * (K - 1)

    for a in A:
      prefix = (prefix + a) % K
      ans += count[prefix]
      count[prefix] += 1

    return ans