Skip to content

2964. Number of Divisible Triplet Sums 👍

  • Time: $O(n^2)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
 public:
  // Similar to 1995. Count Special Quadruplets
  int divisibleTripletCount(vector<int>& nums, int d) {
    int ans = 0;
    unordered_map<int, int> count;

    for (int j = nums.size() - 1; j > 0; --j) {  // 'j' also represents k.
      for (int i = j - 1; i >= 0; --i)
        ans += count[(-(nums[i] + nums[j]) % d + d) % d];
      ++count[nums[j] % d];  // j := k
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
  // Similar to 1995. Count Special Quadruplets
  public int divisibleTripletCount(int[] nums, int d) {
    int ans = 0;
    Map<Integer, Integer> count = new HashMap<>();

    for (int j = nums.length - 1; j > 0; --j) { // 'j' also represents k.
      for (int i = j - 1; i >= 0; --i)
        ans += count.getOrDefault((-(nums[i] + nums[j]) % d + d) % d, 0);
      count.merge(nums[j] % d, 1, Integer::sum); // j := k
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  # Similar to 1995. Count Special Quadruplets
  def divisibleTripletCount(self, nums: list[int], d: int) -> int:
    ans = 0
    count = collections.Counter()

    for j in range(len(nums) - 1, 0, -1):  # `j` also represents k.
      for i in range(j - 1, -1, -1):
        ans += count[-(nums[i] + nums[j]) % d]
      count[nums[j] % d] += 1  # j := k

    return ans