Number of Single Divisor Triplets
MediumUpdated: Aug 2, 2025
Practice on:
Problem
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 ofsingle divisor triplets of _nums .
Examples
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 <= 10^51 <= nums[i] <= 100
Solution
Method 1 – Counting with Frequency Array
Intuition
Since all numbers are between 1 and 100, we can count the frequency of each number and enumerate all possible triplets of values (a, b, c). For each triplet, we check if the sum is divisible by exactly one of a, b, or c, and count the number of index permutations using the frequencies.
Approach
- Count the frequency of each number in
nums(from 1 to 100). - For all ordered triplets (a, b, c) with possible repetitions, check:
- All indices are distinct (i, j, k), but values can repeat.
- For each (a, b, c), compute
s = a + b + c. - Count how many of (a, b, c) divide
s. - If exactly one divides, add the number of index permutations for (a, b, c) to the answer.
- For (a, b, c) all different, count = freq[a] * freq[b] * freq[c] * 6. For two equal, count = freq[a] * (freq[a]-1) * freq[b] * 3 (choose which two are equal). For all equal, skip (since s is always divisible by all three).
- Return the total count.
Code
C++
class Solution {
public:
long long singleDivisorTriplet(vector<int>& nums) {
vector<long long> cnt(101, 0);
for (int x : nums) cnt[x]++;
long long ans = 0;
for (int a = 1; a <= 100; ++a) if (cnt[a])
for (int b = 1; b <= 100; ++b) if (cnt[b])
for (int c = 1; c <= 100; ++c) if (cnt[c]) {
int s = a + b + c;
int d = (s%a==0)+(s%b==0)+(s%c==0);
if (d == 1) {
if (a == b && b == c) continue;
else if (a == b) ans += cnt[a]*(cnt[a]-1)*cnt[c]*3;
else if (a == c) ans += cnt[a]*(cnt[a]-1)*cnt[b]*3;
else if (b == c) ans += cnt[b]*(cnt[b]-1)*cnt[a]*3;
else ans += cnt[a]*cnt[b]*cnt[c]*6;
}
}
return ans;
}
};
Go
func singleDivisorTriplet(nums []int) int64 {
cnt := make([]int64, 101)
for _, x := range nums {
cnt[x]++
}
var ans int64
for a := 1; a <= 100; a++ {
if cnt[a] == 0 { continue }
for b := 1; b <= 100; b++ {
if cnt[b] == 0 { continue }
for c := 1; c <= 100; c++ {
if cnt[c] == 0 { continue }
s := a + b + c
d := 0
if s%a == 0 { d++ }
if s%b == 0 { d++ }
if s%c == 0 { d++ }
if d == 1 {
if a == b && b == c { continue }
if a == b {
ans += cnt[a]*(cnt[a]-1)*cnt[c]*3
} else if a == c {
ans += cnt[a]*(cnt[a]-1)*cnt[b]*3
} else if b == c {
ans += cnt[b]*(cnt[b]-1)*cnt[a]*3
} else {
ans += cnt[a]*cnt[b]*cnt[c]*6
}
}
}
}
}
return ans
}
Java
class Solution {
public long singleDivisorTriplet(int[] nums) {
long[] cnt = new long[101];
for (int x : nums) cnt[x]++;
long ans = 0;
for (int a = 1; a <= 100; ++a) if (cnt[a] > 0)
for (int b = 1; b <= 100; ++b) if (cnt[b] > 0)
for (int c = 1; c <= 100; ++c) if (cnt[c] > 0) {
int s = a + b + c;
int d = 0;
if (s % a == 0) d++;
if (s % b == 0) d++;
if (s % c == 0) d++;
if (d == 1) {
if (a == b && b == c) continue;
else if (a == b) ans += cnt[a]*(cnt[a]-1)*cnt[c]*3;
else if (a == c) ans += cnt[a]*(cnt[a]-1)*cnt[b]*3;
else if (b == c) ans += cnt[b]*(cnt[b]-1)*cnt[a]*3;
else ans += cnt[a]*cnt[b]*cnt[c]*6;
}
}
return ans;
}
}
Kotlin
class Solution {
fun singleDivisorTriplet(nums: IntArray): Long {
val cnt = LongArray(101)
for (x in nums) cnt[x]++
var ans = 0L
for (a in 1..100) if (cnt[a]>0)
for (b in 1..100) if (cnt[b]>0)
for (c in 1..100) if (cnt[c]>0) {
val s = a + b + c
var d = 0
if (s % a == 0) d++
if (s % b == 0) d++
if (s % c == 0) d++
if (d == 1) {
if (a == b && b == c) continue
else if (a == b) ans += cnt[a]*(cnt[a]-1)*cnt[c]*3
else if (a == c) ans += cnt[a]*(cnt[a]-1)*cnt[b]*3
else if (b == c) ans += cnt[b]*(cnt[b]-1)*cnt[a]*3
else ans += cnt[a]*cnt[b]*cnt[c]*6
}
}
return ans
}
}
Python
class Solution:
def singleDivisorTriplet(self, nums: list[int]) -> int:
cnt = [0]*101
for x in nums:
cnt[x] += 1
ans = 0
for a in range(1, 101):
if cnt[a] == 0: continue
for b in range(1, 101):
if cnt[b] == 0: continue
for c in range(1, 101):
if cnt[c] == 0: continue
s = a + b + c
d = (s%a==0) + (s%b==0) + (s%c==0)
if d == 1:
if a == b == c: continue
elif a == b:
ans += cnt[a]*(cnt[a]-1)*cnt[c]*3
elif a == c:
ans += cnt[a]*(cnt[a]-1)*cnt[b]*3
elif b == c:
ans += cnt[b]*(cnt[b]-1)*cnt[a]*3
else:
ans += cnt[a]*cnt[b]*cnt[c]*6
return ans
Rust
impl Solution {
pub fn single_divisor_triplet(nums: Vec<i32>) -> i64 {
let mut cnt = vec![0i64; 101];
for &x in &nums { cnt[x as usize] += 1; }
let mut ans = 0i64;
for a in 1..=100 {
if cnt[a] == 0 { continue; }
for b in 1..=100 {
if cnt[b] == 0 { continue; }
for c in 1..=100 {
if cnt[c] == 0 { continue; }
let s = a + b + c;
let d = (s%a==0) as i32 + (s%b==0) as i32 + (s%c==0) as i32;
if d == 1 {
if a == b && b == c { continue; }
else if a == b { ans += cnt[a]*(cnt[a]-1)*cnt[c]*3; }
else if a == c { ans += cnt[a]*(cnt[a]-1)*cnt[b]*3; }
else if b == c { ans += cnt[b]*(cnt[b]-1)*cnt[a]*3; }
else { ans += cnt[a]*cnt[b]*cnt[c]*6; }
}
}
}
}
ans
}
}
TypeScript
class Solution {
singleDivisorTriplet(nums: number[]): number {
const cnt = Array(101).fill(0);
for (const x of nums) cnt[x]++;
let ans = 0;
for (let a = 1; a <= 100; ++a) if (cnt[a])
for (let b = 1; b <= 100; ++b) if (cnt[b])
for (let c = 1; c <= 100; ++c) if (cnt[c]) {
const s = a + b + c;
const d = +(s%a===0) + +(s%b===0) + +(s%c===0);
if (d === 1) {
if (a === b && b === c) continue;
else if (a === b) ans += cnt[a]*(cnt[a]-1)*cnt[c]*3;
else if (a === c) ans += cnt[a]*(cnt[a]-1)*cnt[b]*3;
else if (b === c) ans += cnt[b]*(cnt[b]-1)*cnt[a]*3;
else ans += cnt[a]*cnt[b]*cnt[c]*6;
}
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(100^3) = O(1), since the value range is fixed and small. Counting frequencies isO(n). - 🧺 Space complexity:
O(1), for the frequency array (size 101).