Skip to main content
Talentd

Number of Single Divisor Triplets - Solution & Explanation

MediumPremiumFree on FleetCodeMath13 min read
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You receive an integer array nums. Count triplets (i, j, k) such that exactly one of nums[i], nums[j], or nums[k] divides the sum nums[i] + nums[j] + nums[k]. The challenge is checking the divisor condition while efficiently counting all valid index permutations.

Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)

Iterate over every triplet of indices using three nested loops. For each combination, compute sum = a + b + c. Check the divisibility conditions sum % a, sum % b, and sum % c. Count the triplet only if exactly one of these values equals zero. This approach directly follows the problem definition and is useful for validating logic on small inputs. The downside is the cubic time complexity, which becomes impractical when n grows large.

Approach 2: Counting + Enumeration (O(U^3) time, O(U) space)

Instead of iterating over indices, count how many times each value appears using a frequency array or hash map. Let U be the number of distinct values (bounded and much smaller than n in typical constraints). Enumerate all value triples (a, b, c) with non‑zero frequencies and compute s = a + b + c. Check how many of a, b, and c divide s. If exactly one does, multiply by the number of index permutations derived from their frequencies. Handle cases separately where values are equal (a == b, b == c, etc.) using combinatorics. This converts expensive index enumeration into value-based counting.

The key insight is that divisibility depends only on the values, not the positions. By grouping identical numbers first, you avoid repeatedly evaluating the same triplet pattern. This technique is common in counting problems and math-based enumeration, where you trade direct iteration for frequency aggregation and combinatorial counting. The divisibility check itself is simple arithmetic, often seen in number theory style interview questions.

Recommended for interviews: Start by describing the brute force O(n^3) approach to demonstrate understanding of the condition. Then transition to the counting + enumeration strategy. Interviewers typically expect the optimized solution because it removes redundant work and shows comfort with frequency maps and combinatorics.

Solution

We notice that the range of elements in the array nums is [1, 100]. Therefore, we can enumerate three numbers a, b, c, where a, b, c \in [1, 100], and then determine whether a + b + c can only be divided by one of a, b, c. If so, we can calculate the number of single-factor triples with a, b, c as elements. The specific calculation method is as follows:

  • If a = b, then the number of single-factor triples with a, b, c as elements is x times (x - 1) times z, where x, y, z represent the number of occurrences of a, b, c in the array nums respectively.
  • If a = c, then the number of single-factor triples with a, b, c as elements is x times (x - 1) times y.
  • If b = c, then the number of single-factor triples with a, b, c as elements is x times y times (y - 1).
  • If a, b, c are all different, then the number of single-factor triples with a, b, c as elements is x times y times z.

Finally, we add up the numbers of all single-factor triples.

The time complexity is O(M^3), and the space complexity is O(M). Where M is the range of elements in the array nums.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Triplet EnumerationO(n^3)O(1)Useful for understanding the condition or validating correctness on small inputs
Counting + EnumerationO(U^3)O(U)Best practical solution when many values repeat and the value range is small

Video Solution

2198. Number of Single Divisor Triplets (Leetcode Medium) • Programming Live with Larry • 111 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Number of Single Divisor Triplets easy or hard?
The problem is rated Medium because the brute force logic is straightforward but the optimized solution requires careful counting and combinatorial reasoning. Handling duplicate values and computing the correct number of index permutations adds extra complexity.
Number of Single Divisor Triplets Python/Java solution
Most implementations build a frequency array, iterate through all possible value triples (a, b, c), compute the sum, and check how many of a, b, and c divide that sum. If exactly one divisor condition holds, multiply by the number of permutations derived from their frequencies. The same logic works in Python, Java, C++, Go, and TypeScript.
How to solve Number of Single Divisor Triplets in O(n)?
A strict O(n) algorithm is not typical for this problem because the divisor condition depends on combinations of three numbers. The common optimized solution uses a frequency array and enumerates value triples, achieving roughly O(U^3) time where U is the distinct value count. This is much faster than checking all n^3 index triplets when many numbers repeat.
What is the best approach for Number of Single Divisor Triplets?
The most efficient approach is counting + enumeration. First compute the frequency of each value in the array, then enumerate value triplets (a, b, c) instead of index triplets. For each combination, check whether exactly one value divides the sum a + b + c and multiply by the number of index permutations. This reduces repeated work and runs in about O(U^3) time where U is the number of distinct values.
Is Number of Single Divisor Triplets asked at Google/Amazon/Meta?
Problems involving combinatorics and divisibility conditions appear frequently in interviews at large tech companies. Variants that combine counting, enumeration, and modular arithmetic have shown up in interviews at companies like Amazon and Google. The question tests reasoning about arithmetic constraints and efficient counting.
What data structure is used in Number of Single Divisor Triplets?
The core data structure is a frequency map or fixed-size counting array. It stores how many times each number appears in the input. This allows the algorithm to enumerate unique value combinations and compute how many index triplets they represent using combinatorics.
What is the time complexity of Number of Single Divisor Triplets?
A direct brute force solution requires O(n^3) time because every triplet of indices must be checked. The optimized counting approach reduces the search space by enumerating value combinations instead of indices, giving O(U^3) time where U is the number of unique values. Space complexity is O(U) for storing frequencies.

Ready to solve this problem?

Practice Number of Single Divisor Triplets with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Array Pairs Divisible by K