LeetCode Solutions

974. Subarray Sums Divisible by K

Time:

Space:

			

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;
  }
};
			

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;
  }
}
			

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