2198. Number of Single Divisor Triplets π
Description
You are given a 0-indexed array of positive integers nums
. A triplet of three distinct indices (i, j, k)
is called a single divisor triplet of nums
if nums[i] + nums[j] + nums[k]
is divisible by exactly one of nums[i]
, nums[j]
, or nums[k]
.
Return the number of single divisor triplets of nums
.
Example 1:
Input: nums = [4,6,7,3,2] Output: 12 Explanation: The triplets (0, 3, 4), (0, 4, 3), (3, 0, 4), (3, 4, 0), (4, 0, 3), and (4, 3, 0) have the values of [4, 3, 2] (or a permutation of [4, 3, 2]). 4 + 3 + 2 = 9 which is only divisible by 3, so all such triplets are single divisor triplets. The triplets (0, 2, 3), (0, 3, 2), (2, 0, 3), (2, 3, 0), (3, 0, 2), and (3, 2, 0) have the values of [4, 7, 3] (or a permutation of [4, 7, 3]). 4 + 7 + 3 = 14 which is only divisible by 7, so all such triplets are single divisor triplets. There are 12 single divisor triplets in total.
Example 2:
Input: nums = [1,2,2] Output: 6 Explanation: The triplets (0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), and (2, 1, 0) have the values of [1, 2, 2] (or a permutation of [1, 2, 2]). 1 + 2 + 2 = 5 which is only divisible by 1, so all such triplets are single divisor triplets. There are 6 single divisor triplets in total.
Example 3:
Input: nums = [1,1,1] Output: 0 Explanation: There are no single divisor triplets. Note that (0, 1, 2) is not a single divisor triplet because nums[0] + nums[1] + nums[2] = 3 and 3 is divisible by nums[0], nums[1], and nums[2].
Constraints:
3 <= nums.length <= 105
1 <= nums[i] <= 100
Solutions
Solution 1: Counting + Enumeration
We notice that the range of elements in the array nums
is $[1, 100]$. Therefore, we can enumerate three numbers $a, b, c$, where $a, b, c \in [1, 100]$, and then determine whether $a + b + c$ can only be divided by one of $a, b, c$. If so, we can calculate the number of single-factor triples with $a, b, c$ as elements. The specific calculation method is as follows:
- If $a = b$, then the number of single-factor triples with $a, b, c$ as elements is $x \times (x - 1) \times z$, where $x$, $y$, $z$ represent the number of occurrences of $a$, $b$, $c$ in the array
nums
respectively. - If $a = c$, then the number of single-factor triples with $a, b, c$ as elements is $x \times (x - 1) \times y$.
- If $b = c$, then the number of single-factor triples with $a, b, c$ as elements is $x \times y \times (y - 1)$.
- If $a, b, c$ are all different, then the number of single-factor triples with $a, b, c$ as elements is $x \times y \times z$.
Finally, we add up the numbers of all single-factor triples.
The time complexity is $O(M^3)$, and the space complexity is $O(M)$. Where $M$ is the range of elements in the array nums
.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
|