2964. Number of Divisible Triplet Sums π
Description
Given a 0-indexed integer array nums
and an integer d
, return the number of triplets (i, j, k)
such that i < j < k
and (nums[i] + nums[j] + nums[k]) % d == 0
.
Example 1:
Input: nums = [3,3,4,7,8], d = 5 Output: 3 Explanation: The triplets which are divisible by 5 are: (0, 1, 2), (0, 2, 4), (1, 2, 4). It can be shown that no other triplet is divisible by 5. Hence, the answer is 3.
Example 2:
Input: nums = [3,3,3,3], d = 3 Output: 4 Explanation: Any triplet chosen here has a sum of 9, which is divisible by 3. Hence, the answer is the total number of triplets which is 4.
Example 3:
Input: nums = [3,3,3,3], d = 6 Output: 0 Explanation: Any triplet chosen here has a sum of 9, which is not divisible by 6. Hence, the answer is 0.
Constraints:
1 <= nums.length <= 1000
1 <= nums[i] <= 109
1 <= d <= 109
Solutions
Solution 1: Hash Table + Enumeration
We can use a hash table $cnt$ to record the occurrence times of $nums[i] \bmod d$, then enumerate $j$ and $k$, calculate the value of $nums[i] \bmod d$ that makes the equation $(nums[i] + nums[j] + nums[k]) \bmod d = 0$ hold, which is $(d - (nums[j] + nums[k]) \bmod d) \bmod d$, and accumulate its occurrence times to the answer. Then we increase the occurrence times of $nums[j] \bmod d$ by one. Continue to enumerate $j$ and $k$ until $j$ reaches the end of the array.
The time complexity is $O(n^2)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array $nums$.
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|