LeetCode 2198 - Number of Single Divisor Triplets

The problem asks us to count how many ordered triplets of distinct indices (i, j, k) satisfy a very specific divisibility condition.

leetcodemediumarraycountingenumeration

LeetCode Problem 2198

Difficulty: 🟡 Medium
Topics: Array, Counting, Enumeration

Solution

Problem Understanding

The problem asks us to count how many ordered triplets of distinct indices (i, j, k) satisfy a very specific divisibility condition.

For every triplet, we compute:

$$\text{sum} = nums[i] + nums[j] + nums[k]$$

The triplet is considered valid if this sum is divisible by exactly one of the three participating values:

  • nums[i]
  • nums[j]
  • nums[k]

The indices must all be distinct, meaning we cannot reuse the same array position multiple times, even if values are equal.

An important detail is that the problem counts ordered triplets, not unordered combinations. This means (0,1,2) and (2,1,0) are considered different triplets. If a value combination works, every valid permutation of the corresponding indices contributes separately to the answer.

The input size is large:

  • nums.length can be up to 10^5
  • nums[i] is at most 100

This constraint is the key observation of the entire problem. Although the array itself is huge, the value range is extremely small. Instead of thinking in terms of indices, we should think in terms of frequencies of values.

Several edge cases are important:

  • Arrays with many duplicates, such as [1,2,2]
  • Arrays where all values are identical
  • Triplets where two or all three values are equal
  • Values equal to 1, since every integer is divisible by 1
  • Large arrays where brute force enumeration is impossible

The bounded value range strongly suggests using counting and frequency-based enumeration instead of iterating over all index triplets.

Approaches

Brute Force Approach

The most direct solution is to try every possible triplet of distinct indices.

For every triple (i, j, k):

  1. Compute the sum.
  2. Check whether the sum is divisible by nums[i].
  3. Check whether the sum is divisible by nums[j].
  4. Check whether the sum is divisible by nums[k].
  5. Count how many of these divisibility checks succeed.
  6. If exactly one succeeds, increment the answer.

This works because it literally follows the definition of the problem.

However, the time complexity is far too large. There are:

$$O(n^3)$$

possible triplets, and n can be 100000. A cubic solution is completely infeasible.

Key Insight

The critical observation is that every number is between 1 and 100.

That means there are only 100 distinct possible values in the entire array.

Instead of iterating over indices, we can iterate over value combinations:

$$(a, b, c)$$

where each value is between 1 and 100.

There are at most:

$$100^3 = 1,000,000$$

value triplets, which is manageable.

For each value triplet:

  1. Check whether a + b + c is divisible by exactly one of them.
  2. Compute how many index triplets can produce this value combination using frequency counts.
  3. Add the appropriate number of permutations.

This transforms an impossible O(n^3) solution into a practical constant-bounded counting solution.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n³) O(1) Enumerates every index triplet directly
Optimal O(100³) O(100) Uses frequency counting and value enumeration

Algorithm Walkthrough

Step 1: Count Frequencies

Create a frequency array or hash map storing how many times each value appears.

Since values are only between 1 and 100, a fixed-size array is ideal.

For example:

nums = [1,2,2]

produces:

freq[1] = 1
freq[2] = 2

This allows us to compute how many index selections are possible for any value combination.

Step 2: Enumerate All Value Triplets

Iterate through all possible values:

a from 1 to 100
b from 1 to 100
c from 1 to 100

Skip any value whose frequency is zero.

At this stage we are considering value combinations, not actual indices.

Step 3: Check the Divisibility Condition

Compute:

$$s = a + b + c$$

Now count how many of these are divisors of s:

  • s % a == 0
  • s % b == 0
  • s % c == 0

If exactly one condition is true, the triplet is valid.

Step 4: Compute How Many Index Triplets Exist

Now determine how many distinct index triplets correspond to (a,b,c).

There are three cases.

Case 1: All Values Distinct

If:

a != b != c

then the number of ordered index triplets is:

$$freq[a] \times freq[b] \times freq[c]$$

because each chosen index is automatically distinct.

Case 2: Two Values Equal

Suppose:

a == b != c

Then we must choose two distinct indices for value a.

The count becomes:

$$freq[a] \times (freq[a]-1) \times freq[c]$$

The same logic applies to the other equality patterns.

Case 3: All Values Equal

If:

a == b == c

we need three distinct indices:

$$freq[a] \times (freq[a]-1) \times (freq[a]-2)$$

Step 5: Add the Count

Add all valid ordered triplet counts into the final answer.

Because we are already iterating over ordered value triplets (a,b,c), permutations are naturally included.

Why it works

The algorithm works because every valid ordered index triplet corresponds to exactly one ordered value triplet (a,b,c).

The divisibility test depends only on the values, not the indices themselves. Therefore we can evaluate validity once per value combination and then multiply by the number of index arrangements that realize that combination.

Since the frequency formulas correctly count distinct index selections for all equality patterns, every valid triplet is counted exactly once.

Python Solution

from typing import List

class Solution:
    def singleDivisorTriplet(self, nums: List[int]) -> int:
        freq = [0] * 101
        
        for num in nums:
            freq[num] += 1
        
        answer = 0
        
        for a in range(1, 101):
            if freq[a] == 0:
                continue
                
            for b in range(1, 101):
                if freq[b] == 0:
                    continue
                    
                for c in range(1, 101):
                    if freq[c] == 0:
                        continue
                    
                    total = a + b + c
                    
                    divisible_count = 0
                    
                    if total % a == 0:
                        divisible_count += 1
                    if total % b == 0:
                        divisible_count += 1
                    if total % c == 0:
                        divisible_count += 1
                    
                    if divisible_count != 1:
                        continue
                    
                    if a == b == c:
                        if freq[a] >= 3:
                            answer += (
                                freq[a]
                                * (freq[a] - 1)
                                * (freq[a] - 2)
                            )
                    
                    elif a == b:
                        if freq[a] >= 2:
                            answer += (
                                freq[a]
                                * (freq[a] - 1)
                                * freq[c]
                            )
                    
                    elif a == c:
                        if freq[a] >= 2:
                            answer += (
                                freq[a]
                                * (freq[a] - 1)
                                * freq[b]
                            )
                    
                    elif b == c:
                        if freq[b] >= 2:
                            answer += (
                                freq[a]
                                * freq[b]
                                * (freq[b] - 1)
                            )
                    
                    else:
                        answer += freq[a] * freq[b] * freq[c]
        
        return answer

The implementation begins by building a frequency array for all possible values from 1 to 100. This converts the problem from index-based enumeration into value-based counting.

The three nested loops enumerate every ordered value triplet (a,b,c). Since the value range is fixed and tiny, this is efficient enough.

For each triplet, the code computes the total sum and counts how many of the three values divide that sum. Only combinations where exactly one divisor condition holds are kept.

The next section determines how many actual index triplets correspond to the current value combination. The implementation carefully handles the three equality cases separately:

  • all equal
  • exactly two equal
  • all distinct

This ensures indices remain distinct while preserving ordered permutations.

Finally, the computed count is added into the running total.

Go Solution

func singleDivisorTriplet(nums []int) int64 {
    freq := make([]int64, 101)

    for _, num := range nums {
        freq[num]++
    }

    var answer int64 = 0

    for a := 1; a <= 100; a++ {
        if freq[a] == 0 {
            continue
        }

        for b := 1; b <= 100; b++ {
            if freq[b] == 0 {
                continue
            }

            for c := 1; c <= 100; c++ {
                if freq[c] == 0 {
                    continue
                }

                total := a + b + c

                divisibleCount := 0

                if total%a == 0 {
                    divisibleCount++
                }

                if total%b == 0 {
                    divisibleCount++
                }

                if total%c == 0 {
                    divisibleCount++
                }

                if divisibleCount != 1 {
                    continue
                }

                if a == b && b == c {
                    if freq[a] >= 3 {
                        answer += freq[a] *
                            (freq[a] - 1) *
                            (freq[a] - 2)
                    }

                } else if a == b {
                    if freq[a] >= 2 {
                        answer += freq[a] *
                            (freq[a] - 1) *
                            freq[c]
                    }

                } else if a == c {
                    if freq[a] >= 2 {
                        answer += freq[a] *
                            (freq[a] - 1) *
                            freq[b]
                    }

                } else if b == c {
                    if freq[b] >= 2 {
                        answer += freq[a] *
                            freq[b] *
                            (freq[b] - 1)
                    }

                } else {
                    answer += freq[a] * freq[b] * freq[c]
                }
            }
        }
    }

    return answer
}

The Go version follows the same logic as the Python implementation. One important difference is that the function returns int64, so the frequency array and answer variable also use int64 to avoid overflow during multiplication.

Go arrays and slices are initialized with zero values automatically, which simplifies frequency counting.

Worked Examples

Example 1

nums = [4,6,7,3,2]

Frequency Table

Value Frequency
2 1
3 1
4 1
6 1
7 1

Consider value triplet (4,3,2).

Step 1: Compute Sum

a b c Sum
4 3 2 9

Step 2: Divisibility Check

Divisor Result
9 % 4 1
9 % 3 0
9 % 2 1

Exactly one divisor works, namely 3.

Step 3: Count Ordered Index Triplets

All values are distinct.

$$1 \times 1 \times 1 = 1$$

But permutations are separately enumerated:

(4,3,2)
(4,2,3)
(3,4,2)
(3,2,4)
(2,4,3)
(2,3,4)

So this contributes 6.

Now consider (4,7,3).

Sum

$$4 + 7 + 3 = 14$$

Divisibility

Divisor Result
14 % 4 2
14 % 7 0
14 % 3 2

Exactly one divisor works again.

This contributes another 6.

Final answer:

6 + 6 = 12

Example 2

nums = [1,2,2]

Frequency Table

Value Frequency
1 1
2 2

Consider (1,2,2).

Sum

$$1 + 2 + 2 = 5$$

Divisibility

Divisor Result
5 % 1 0
5 % 2 1
5 % 2 1

Exactly one divisor works.

Count Index Arrangements

Two values are equal.

$$1 \times 2 \times 1 = 2$$

Accounting for ordered permutations gives:

3! = 6

The algorithm naturally counts all six ordered arrangements during enumeration.

Final answer:

6

Example 3

nums = [1,1,1]

Frequency Table

Value Frequency
1 3

Consider (1,1,1).

Sum

$$1 + 1 + 1 = 3$$

Divisibility

Divisor Result
3 % 1 0
3 % 1 0
3 % 1 0

All three divide the sum.

The condition requires exactly one divisor.

Therefore this triplet is invalid.

Final answer:

0

Complexity Analysis

Measure Complexity Explanation
Time O(100³) Enumerates all possible value triplets
Space O(100) Frequency array for values 1 through 100

The algorithm's runtime is effectively constant because the value range is fixed at 100. Even though there are three nested loops, the maximum number of iterations is only one million, which is entirely practical.

The space usage is also constant because the frequency array size never grows with the input length.

Test Cases

sol = Solution()

assert sol.singleDivisorTriplet([4,6,7,3,2]) == 12
# Basic mixed-values example from problem statement

assert sol.singleDivisorTriplet([1,2,2]) == 6
# Duplicate values with valid permutations

assert sol.singleDivisorTriplet([1,1,1]) == 0
# All divisors work, should be invalid

assert sol.singleDivisorTriplet([2,2,2]) == 0
# Sum divisible by all three equal values

assert sol.singleDivisorTriplet([1,1,2]) == 0
# Sum = 4, divisible by both 1s and 2

assert sol.singleDivisorTriplet([2,3,5]) == 6
# Sum = 10, divisible only by 5

assert sol.singleDivisorTriplet([3,4,5]) == 0
# Sum = 12, divisible by both 3 and 4

assert sol.singleDivisorTriplet([1,2,3]) == 0
# Sum = 6, divisible by all three

assert sol.singleDivisorTriplet([7,8,9]) == 6
# Sum = 24, divisible only by 8

assert sol.singleDivisorTriplet([100,100,99]) == 0
# Large values near constraint boundary

assert sol.singleDivisorTriplet([1,2,2,2]) == 18
# Multiple duplicate indices create more permutations

assert sol.singleDivisorTriplet([5,10,15]) == 0
# Sum divisible by all three values

Test Summary

Test Why
[4,6,7,3,2] Verifies official example
[1,2,2] Tests duplicate handling
[1,1,1] Ensures exactly-one condition is enforced
[2,2,2] Tests all-equal invalid case
[1,1,2] Tests multiple divisibility matches
[2,3,5] Tests valid distinct triplet
[3,4,5] Tests invalid distinct triplet
[1,2,3] Tests divisibility by all values
[7,8,9] Tests another valid distinct case
[100,100,99] Tests upper value boundary
[1,2,2,2] Tests many duplicate index arrangements
[5,10,15] Tests another fully divisible case

Edge Cases

All Values Equal

An array like:

[1,1,1]

is a common source of mistakes because every divisor check behaves identically. A naive implementation may accidentally treat this as valid if it only checks whether at least one divisor works. The problem specifically requires exactly one divisor.

The implementation handles this correctly by counting the number of successful divisibility checks and requiring the count to equal exactly 1.

Duplicate Values with Distinct Indices

Arrays such as:

[1,2,2]

require careful handling because equal values can still come from different indices. A common bug is undercounting permutations or failing to enforce distinct indices.

The implementation explicitly uses permutation-style counting formulas:

$$freq[x] \times (freq[x]-1)$$

when two equal values are needed. This guarantees different indices are selected.

Value 1

The value 1 is special because every integer is divisible by 1.

This means any triplet containing multiple 1s can easily violate the "exactly one divisor" rule. For example:

[1,1,2]

produces sum 4, which is divisible by both 1 and 2.

The implementation avoids errors by independently checking divisibility for each position and counting how many succeed, rather than assuming divisibility behavior from the values alone.