Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2198.html

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

  • 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
}

All Problems

All Solutions