Welcome to Subscribe On Youtube
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 <= 1051 <= nums[i] <= 100
Solutions
-
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; } } -
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; } }; -
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 -
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 } -
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; }