Welcome to Subscribe On Youtube

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
• Go
• TypeScript

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

• class Solution:
      def subarraysDivByK(self, nums: List[int], k: int) -> int:
          ans = s = 0
          counter = Counter({0: 1})
          for num in nums:
              s += num
              ans += counter[s % k]
              counter[s % k] += 1
          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
  
  

• func subarraysDivByK(nums []int, k int) (ans int) {
  	cnt := map[int]int{0: 1}
  	s := 0
  	for _, x := range nums {
  		s = ((s+x)%k + k) % k
  		ans += cnt[s]
  		cnt[s]++
  	}
  	return
  }
  

• function subarraysDivByK(nums: number[], k: number): number {
      const counter = new Map();
      counter.set(0, 1);
      let s = 0,
          ans = 0;
      for (const num of nums) {
          s += num;
          const t = ((s % k) + k) % k;
          ans += counter.get(t) || 0;
          counter.set(t, (counter.get(t) || 0) + 1);
      }
      return ans;
  }
  
  

All Problems

All Solutions