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:

1
2
3
4
5
6
7

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:

1
2
3
4
5
6

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:

1
2
3
4
5

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^5
  • 1 <= 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

  1. Count the frequency of each number in nums (from 1 to 100).
  2. 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.
  3. 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).
  4. Return the total count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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

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

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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 is O(n).
  • 🧺 Space complexity: O(1), for the frequency array (size 101).