Formatted question description: https://leetcode.ca/all/974.html

974. Subarray Sums Divisible by K

Level

Medium

Description

Given an array A of integers, return the number of (contiguous, non-empty) subarrays that have a sum divisible by K.

Example 1:

Input: A = [4,5,0,-2,-3,1], K = 5

Output: 7

Explanation: There are 7 subarrays with a sum divisible by K = 5: [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

Note:

1. 1 <= A.length <= 30000
2. -10000 <= A[i] <= 10000
3. 2 <= K <= 10000

Solution

This problem is similar to problem 560, and the solution is also similar to the solution to problem 560.

Use a map to store each sum’s remainder divided by K and the count of subarrays of the remainder. Put sum 0 with count 1 to the map initially.

Loop over nums and calculate the total sum’s remainder sum. For each num in nums, add num to sum and calculate sum = sum % K and make sure sum is nonnegative, and obtain the count of subarrays with sum remainder sum. Add the sum to the result. Then update the map with the count of subarrays with sum remainder sum. Finally, return the result.

• Java
• C++
• Python

• class Solution {
      public int subarraysDivByK(int[] A, int K) {
          Map<Integer, Integer> map = new HashMap<Integer, Integer>();
          map.put(0, 1);
          int count = 0;
          int sum = 0;
          int length = A.length;
          for (int i = 0; i < length; i++) {
              int curRemainder = A[i] % K;
              if (curRemainder < 0)
                  curRemainder += K;
              sum = (sum + curRemainder) % K;
              int curCount = map.getOrDefault(sum, 0);
              count += curCount;
              map.put(sum, curCount + 1);
          }
          return count;
      }
  }
  

• // OJ: https://leetcode.com/problems/subarray-sums-divisible-by-k/
  // Time: O(N)
  // Space: O(K)
  class Solution {
  public:
      int subarraysDivByK(vector<int>& A, int k) {
          unordered_map<int, int> m{ {0,1} };
          int sum = 0, ans = 0;
          for (int n : A) {
              sum += n;
              if (sum >= 0) sum %= k;
              else sum = (k - (-sum % k)) % k;
              ans += m[sum];
              m[sum]++;
          }
          return ans;
      }
  };
  

• # 974. Subarray Sums Divisible by K
  # https://leetcode.com/problems/subarray-sums-divisible-by-k/
  
  class Solution:
      def subarraysDivByK(self, nums: List[int], k: int) -> int:
          mp = collections.defaultdict(int)
          mp[0] = 1
          res = s = 0
          
          for x in nums:
              s = (s + x) % k
              
              res += mp[s]
              
              mp[s] += 1
              
          return res
  
  

All Problems

All Solutions