Number of Single Divisor Triplets - Video Solutions

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.