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 <= 1051 <= nums[i] <= 100
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution:
def singleDivisorTriplet(self, nums: List[int]) -> int:
def check(a, b, c):
s = a + b + c
return sum(s % x == 0 for x in [a, b, c]) == 1
counter = Counter(nums)
ans = 0
for a, cnt1 in counter.items():
for b, cnt2 in counter.items():
for c, cnt3 in counter.items():
if check(a, b, c):
if a == b:
ans += cnt1 * (cnt1 - 1) * cnt3
elif a == c:
ans += cnt1 * (cnt1 - 1) * cnt2
elif b == c:
ans += cnt1 * cnt2 * (cnt2 - 1)
else:
ans += cnt1 * cnt2 * cnt3
return ans
|
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
34
35
36
37
38
39
40
| class Solution {
public long singleDivisorTriplet(int[] nums) {
int[] counter = new int[101];
for (int x : nums) {
++counter[x];
}
long ans = 0;
for (int i = 1; i <= 100; ++i) {
for (int j = 1; j <= 100; ++j) {
for (int k = 1; k <= 100; ++k) {
int cnt1 = counter[i], cnt2 = counter[j], cnt3 = counter[k];
int s = i + j + k;
int cnt = 0;
if (s % i == 0) {
++cnt;
}
if (s % j == 0) {
++cnt;
}
if (s % k == 0) {
++cnt;
}
if (cnt != 1) {
continue;
}
if (i == j) {
ans += (long) cnt1 * (cnt1 - 1) * cnt3;
} else if (i == k) {
ans += (long) cnt1 * (cnt1 - 1) * cnt2;
} else if (j == k) {
ans += (long) cnt1 * cnt2 * (cnt2 - 1);
} else {
ans += (long) cnt1 * cnt2 * cnt3;
}
}
}
}
return ans;
}
}
|
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
| class Solution {
public:
long long singleDivisorTriplet(vector<int>& nums) {
vector<int> counter(101);
for (int& x : nums) ++counter[x];
long long ans = 0;
for (int i = 1; i <= 100; ++i) {
for (int j = 1; j <= 100; ++j) {
for (int k = 1; k <= 100; ++k) {
int cnt1 = counter[i], cnt2 = counter[j], cnt3 = counter[k];
int s = i + j + k;
int cnt = (s % i == 0) + (s % j == 0) + (s % k == 0);
if (cnt != 1) continue;
if (i == j)
ans += 1ll * cnt1 * (cnt1 - 1) * cnt3;
else if (i == k)
ans += 1ll * cnt1 * (cnt1 - 1) * cnt2;
else if (j == k)
ans += 1ll * cnt1 * cnt2 * (cnt2 - 1);
else
ans += 1ll * cnt1 * cnt2 * cnt3;
}
}
}
return ans;
}
};
|
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
34
35
36
37
38
39
40
| func singleDivisorTriplet(nums []int) int64 {
counter := make([]int, 101)
for _, x := range nums {
counter[x]++
}
var ans int64
check := func(a, b, c int) bool {
s := a + b + c
cnt := 0
if s%a == 0 {
cnt++
}
if s%b == 0 {
cnt++
}
if s%c == 0 {
cnt++
}
return cnt == 1
}
for i := 1; i <= 100; i++ {
for j := 1; j <= 100; j++ {
for k := 1; k <= 100; k++ {
if check(i, j, k) {
cnt1, cnt2, cnt3 := counter[i], counter[j], counter[k]
if i == j {
ans += int64(cnt1 * (cnt1 - 1) * cnt3)
} else if i == k {
ans += int64(cnt1 * (cnt1 - 1) * cnt2)
} else if j == k {
ans += int64(cnt1 * cnt2 * (cnt2 - 1))
} else {
ans += int64(cnt1 * cnt2 * cnt3)
}
}
}
}
}
return ans
}
|
