Skip to content

2198. Number of Single Divisor Triplets

  • Time: $O(100^3) = O(1)$
  • Space: $O(101) = O(1)$
 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
class Solution {
 public:
  long long singleDivisorTriplet(vector<int>& nums) {
    constexpr int kMax = 100;
    long ans = 0;
    vector<int> count(kMax + 1);

    for (const int num : nums)
      ++count[num];

    for (int a = 1; a <= kMax; ++a)
      for (int b = a; count[a] > 0 && b <= kMax; ++b)
        for (int c = b; count[b] > 0 && c <= kMax; ++c) {
          const int sum = a + b + c;
          if (divisible(sum, a) + divisible(sum, b) + divisible(sum, c) != 1)
            continue;
          if (a == b)
            ans += static_cast<long>(count[a]) * (count[a] - 1) / 2 * count[c];
          else if (b == c)
            ans += static_cast<long>(count[b]) * (count[b] - 1) / 2 * count[a];
          else
            ans += static_cast<long>(count[a]) * count[b] * count[c];
        }

    return ans * 6;
  }

 private:
  int divisible(int sum, int num) {
    return sum % num == 0;
  }
};

 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
class Solution {
  public long singleDivisorTriplet(int[] nums) {
    final int kMax = 100;
    long ans = 0;
    int[] count = new int[kMax + 1];

    for (final int num : nums)
      ++count[num];

    for (int a = 1; a <= kMax; ++a)
      for (int b = a; count[a] > 0 && b <= kMax; ++b)
        for (int c = b; count[b] > 0 && c <= kMax; ++c) {
          final int sum = a + b + c;
          if (divisible(sum, a) + divisible(sum, b) + divisible(sum, c) != 1)
            continue;
          if (a == b)
            ans += (long) count[a] * (count[a] - 1) / 2 * count[c];
          else if (b == c)
            ans += (long) count[b] * (count[b] - 1) / 2 * count[a];
          else
            ans += (long) count[a] * count[b] * count[c];
        }

    return ans * 6;
  }

  private int divisible(int sum, int num) {
    return sum % num == 0 ? 1 : 0;
  }
}

 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
class Solution:
  def singleDivisorTriplet(self, nums: list[int]) -> int:
    ans = 0
    count = collections.Counter(nums)

    def divisible(summ: int, num: int) -> int:
      return summ % num == 0

    for a in range(1, 101):
      if count[a] == 0:
        continue
      for b in range(a, 101):
        if count[b] == 0:
          continue
        for c in range(b, 101):
          if count[c] == 0:
            continue
          summ = a + b + c
          if divisible(summ, a) + divisible(summ, b) + divisible(summ, c) != 1:
            continue
          if a == b:
            ans += count[a] * (count[a] - 1) // 2 * count[c]
          elif b == c:
            ans += count[b] * (count[b] - 1) // 2 * count[a]
          else:
            ans += count[a] * count[b] * count[c]

    return ans * 6