// 974. Subarray Sums Divisible by K #include "leetcode.h" #include /* * 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 &nums, int k) { vector 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 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; }