| comments | difficulty | edit_url | tags | |
|---|---|---|---|---|
true |
Medium |
|
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].
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
We notice that the range of elements in the array nums is
- 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 arraynumsrespectively. - 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 nums.
class Solution:
def singleDivisorTriplet(self, nums: List[int]) -> int:
cnt = Counter(nums)
ans = 0
for a, x in cnt.items():
for b, y in cnt.items():
for c, z in cnt.items():
s = a + b + c
if sum(s % v == 0 for v in (a, b, c)) == 1:
if a == b:
ans += x * (x - 1) * z
elif a == c:
ans += x * (x - 1) * y
elif b == c:
ans += x * y * (y - 1)
else:
ans += x * y * z
return ansclass Solution {
public long singleDivisorTriplet(int[] nums) {
int[] cnt = new int[101];
for (int x : nums) {
++cnt[x];
}
long ans = 0;
for (int a = 1; a <= 100; ++a) {
for (int b = 1; b <= 100; ++b) {
for (int c = 1; c <= 100; ++c) {
int s = a + b + c;
int x = cnt[a], y = cnt[b], z = cnt[c];
int t = 0;
t += s % a == 0 ? 1 : 0;
t += s % b == 0 ? 1 : 0;
t += s % c == 0 ? 1 : 0;
if (t == 1) {
if (a == b) {
ans += 1L * x * (x - 1) * z;
} else if (a == c) {
ans += 1L * x * (x - 1) * y;
} else if (b == c) {
ans += 1L * x * y * (y - 1);
} else {
ans += 1L * x * y * z;
}
}
}
}
}
return ans;
}
}class Solution {
public:
long long singleDivisorTriplet(vector<int>& nums) {
int cnt[101]{};
for (int x : nums) {
++cnt[x];
}
long long ans = 0;
for (int a = 1; a <= 100; ++a) {
for (int b = 1; b <= 100; ++b) {
for (int c = 1; c <= 100; ++c) {
int s = a + b + c;
int x = cnt[a], y = cnt[b], z = cnt[c];
int t = (s % a == 0) + (s % b == 0) + (s % c == 0);
if (t == 1) {
if (a == b) {
ans += 1LL * x * (x - 1) * z;
} else if (a == c) {
ans += 1LL * x * (x - 1) * y;
} else if (b == c) {
ans += 1LL * x * y * (y - 1);
} else {
ans += 1LL * x * y * z;
}
}
}
}
}
return ans;
}
};func singleDivisorTriplet(nums []int) (ans int64) {
cnt := [101]int{}
for _, x := range nums {
cnt[x]++
}
f := func(a, b int) int {
if a%b == 0 {
return 1
}
return 0
}
for a := 1; a <= 100; a++ {
for b := 1; b <= 100; b++ {
for c := 1; c <= 100; c++ {
s := a + b + c
t := f(s, a) + f(s, b) + f(s, c)
if t == 1 {
if a == b {
ans += int64(cnt[a] * (cnt[a] - 1) * cnt[c])
} else if a == c {
ans += int64(cnt[a] * (cnt[a] - 1) * cnt[b])
} else if b == c {
ans += int64(cnt[b] * (cnt[b] - 1) * cnt[a])
} else {
ans += int64(cnt[a] * cnt[b] * cnt[c])
}
}
}
}
}
return
}function singleDivisorTriplet(nums: number[]): number {
const cnt: number[] = Array(101).fill(0);
for (const x of nums) {
++cnt[x];
}
let ans = 0;
const f = (a: number, b: number) => (a % b === 0 ? 1 : 0);
for (let a = 1; a <= 100; ++a) {
for (let b = 1; b <= 100; ++b) {
for (let c = 1; c <= 100; ++c) {
const s = a + b + c;
const t = f(s, a) + f(s, b) + f(s, c);
if (t === 1) {
if (a === b) {
ans += cnt[a] * (cnt[a] - 1) * cnt[c];
} else if (a === c) {
ans += cnt[a] * (cnt[a] - 1) * cnt[b];
} else if (b === c) {
ans += cnt[b] * (cnt[b] - 1) * cnt[a];
} else {
ans += cnt[a] * cnt[b] * cnt[c];
}
}
}
}
}
return ans;
}