Question

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

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

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

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
}