974. Subarray Sums Divisible by K.md

974. Subarray Sums Divisible by K

---

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 <= A.length <= 30000
• -10000 <= A[i] <= 10000
• 2 <= K <= 10000

---

Solution

• mine

  • Java

    Brute Force [Time Limit Exceeded]

    // O(N^2)time O(1)space
    public int subarraysDivByK(int[] A, int K) {
        int res = 0;
        for(int i = 0; i < A.length; i++){
            int sum = 0;
            for(int j = i; j < A.length; j++){
                sum += A[j];
                if(sum % K == 0){
                    res++;
                }
            }
        }
        return res;
    }
    

    Runtime: 4 ms, faster than 95.34%, Memory Usage: 42.1 MB, less than 63.16% of Java online submissions

    //O(N)time O(min(N,K))space
    public int subarraysDivByK(int[] A, int K) {
        int[] map = new int[K];
        map[0] = 1;
        int count = 0, sum = 0;
        for (int a : A) {
            sum = (sum + a) % K;
            if (sum < 0) sum += K;
            count += map[sum];
            map[sum]++;
        }
        return count;
    }
    

---

• the most votes

  Runtime: 19 ms, faster than 51.33%, Memory Usage: 43.3 MB, less than 36.84% of Java online submissions

  //O(N)time O(min(N,K))space
  public int subarraysDivByK(int[] A, int K) {
      Map<Integer, Integer> map = new HashMap<>();
      map.put(0, 1);
      int count = 0, sum = 0;
      for(int a : A) {
          sum = (sum + a) % K;
          if(sum < 0) sum += K;  // Because -1 % 5 = -1, but we need the positive mod 4
          count += map.getOrDefault(sum, 0);
          map.put(sum, map.getOrDefault(sum, 0) + 1);
      }
      return count;
  }
  

  Runtime: 4 ms, faster than 95.34%, Memory Usage: 42.6 MB, less than 52.63% of Java online submissions

  //O(N)time O(min(N,K))space
  public int subarraysDivByK(int[] A, int K) {
      int[] map = new int[K];
      map[0] = 1;
      int count = 0, sum = 0;
      for (int a : A) {
          sum = (sum + a) % K;
          if (sum < 0) sum += K;  // Because -1 % 5 = -1, but we need the positive mod 4
          map[sum]++;
      }
      for (int m : map) {
          if (m == 0) continue;
          count += m * (m - 1) / 2;
      }
      return count;
  }