2198. Number of Single Divisor Triplets - Leetcode Solution

Code Implementation

from collections import Counter

class Solution:
    def singleDivisorTriplet(self, nums):
        count = Counter(nums)
        unique = sorted(count)
        ans = 0

        # All numbers are different
        for i in range(len(unique)):
            for j in range(i+1, len(unique)):
                for k in range(j+1, len(unique)):
                    a, b, c = unique[i], unique[j], unique[k]
                    s = a + b + c
                    if (s % a == 0) + (s % b == 0) + (s % c == 0) == 1:
                        ans += count[a] * count[b] * count[c]

        # Two numbers are the same: (a, a, b)
        for a in unique:
            if count[a] >= 2:
                for b in unique:
                    if b == a:
                        continue
                    s = a + a + b
                    if (s % a == 0) + (s % b == 0) == 1:
                        ans += count[a] * (count[a] - 1) // 2 * count[b]

        # Two numbers are the same: (a, b, b)
        for b in unique:
            if count[b] >= 2:
                for a in unique:
                    if a == b:
                        continue
                    s = a + b + b
                    if (s % a == 0) + (s % b == 0) == 1:
                        ans += count[b] * (count[b] - 1) // 2 * count[a]

        # All numbers are the same: (a, a, a)
        for a in unique:
            if count[a] >= 3:
                s = a * 3
                if (s % a == 0) == 1:  # But s % a == 0 always, so not possible
                    ans += count[a] * (count[a] - 1) * (count[a] - 2) // 6

        return ans

#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

class Solution {
public:
    int singleDivisorTriplet(vector<int>& nums) {
        unordered_map<int, int> count;
        for (int x : nums) count[x]++;
        vector<int> unique;
        for (auto& p : count) unique.push_back(p.first);
        sort(unique.begin(), unique.end());
        int ans = 0, n = unique.size();

        // All numbers are different
        for (int i = 0; i < n; ++i) {
            for (int j = i+1; j < n; ++j) {
                for (int k = j+1; k < n; ++k) {
                    int a = unique[i], b = unique[j], c = unique[k];
                    int s = a + b + c;
                    int cnt = (s % a == 0) + (s % b == 0) + (s % c == 0);
                    if (cnt == 1)
                        ans += count[a] * count[b] * count[c];
                }
            }
        }
        // Two are the same: (a, a, b)
        for (int i = 0; i < n; ++i) {
            int a = unique[i];
            if (count[a] >= 2) {
                for (int j = 0; j < n; ++j) {
                    int b = unique[j];
                    if (a == b) continue;
                    int s = a + a + b;
                    int cnt = (s % a == 0) + (s % b == 0);
                    if (cnt == 1)
                        ans += count[a] * (count[a]-1) / 2 * count[b];
                }
            }
        }
        // Two are the same: (a, b, b)
        for (int j = 0; j < n; ++j) {
            int b = unique[j];
            if (count[b] >= 2) {
                for (int i = 0; i < n; ++i) {
                    int a = unique[i];
                    if (a == b) continue;
                    int s = a + b + b;
                    int cnt = (s % a == 0) + (s % b == 0);
                    if (cnt == 1)
                        ans += count[b] * (count[b]-1) / 2 * count[a];
                }
            }
        }
        // All are the same (a, a, a): always s%a==0, so never exactly one divisor
        return ans;
    }
};

import java.util.*;

class Solution {
    public int singleDivisorTriplet(int[] nums) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int x : nums) count.put(x, count.getOrDefault(x, 0) + 1);
        List<Integer> unique = new ArrayList<>(count.keySet());
        Collections.sort(unique);
        int ans = 0, n = unique.size();

        // All numbers are different
        for (int i = 0; i < n; ++i) {
            for (int j = i+1; j < n; ++j) {
                for (int k = j+1; k < n; ++k) {
                    int a = unique.get(i), b = unique.get(j), c = unique.get(k);
                    int s = a + b + c;
                    int cnt = ((s % a == 0) ? 1 : 0) + ((s % b == 0) ? 1 : 0) + ((s % c == 0) ? 1 : 0);
                    if (cnt == 1)
                        ans += count.get(a) * count.get(b) * count.get(c);
                }
            }
        }
        // Two are the same: (a, a, b)
        for (int i = 0; i < n; ++i) {
            int a = unique.get(i);
            if (count.get(a) >= 2) {
                for (int j = 0; j < n; ++j) {
                    int b = unique.get(j);
                    if (a == b) continue;
                    int s = a + a + b;
                    int cnt = ((s % a == 0) ? 1 : 0) + ((s % b == 0) ? 1 : 0);
                    if (cnt == 1)
                        ans += count.get(a) * (count.get(a) - 1) / 2 * count.get(b);
                }
            }
        }
        // Two are the same: (a, b, b)
        for (int j = 0; j < n; ++j) {
            int b = unique.get(j);
            if (count.get(b) >= 2) {
                for (int i = 0; i < n; ++i) {
                    int a = unique.get(i);
                    if (a == b) continue;
                    int s = a + b + b;
                    int cnt = ((s % a == 0) ? 1 : 0) + ((s % b == 0) ? 1 : 0);
                    if (cnt == 1)
                        ans += count.get(b) * (count.get(b) - 1) / 2 * count.get(a);
                }
            }
        }
        // All are the same: (a, a, a): always s%a==0, so never exactly one divisor
        return ans;
    }
}

var singleDivisorTriplet = function(nums) {
    let count = new Map();
    for (let x of nums) count.set(x, (count.get(x) || 0) + 1);
    let unique = Array.from(count.keys()).sort((a,b) => a-b);
    let ans = 0, n = unique.length;

    // All numbers are different
    for (let i=0; i<n; ++i) {
        for (let j=i+1; j<n; ++j) {
            for (let k=j+1; k<n; ++k) {
                let a = unique[i], b = unique[j], c = unique[k];
                let s = a + b + c;
                let cnt = (s%a==0) + (s%b==0) + (s%c==0);
                if (cnt === 1)
                    ans += count.get(a) * count.get(b) * count.get(c);
            }
        }
    }
    // Two are the same: (a, a, b)
    for (let i=0; i<n; ++i) {
        let a = unique[i];
        if (count.get(a) >= 2) {
            for (let j=0; j<n; ++j) {
                let b = unique[j];
                if (a === b) continue;
                let s = a + a + b;
                let cnt = (s%a==0) + (s%b==0);
                if (cnt === 1)
                    ans += count.get(a) * (count.get(a)-1)/2 * count.get(b);
            }
        }
    }
    // Two are the same: (a, b, b)
    for (let j=0; j<n; ++j) {
        let b = unique[j];
        if (count.get(b) >= 2) {
            for (let i=0; i<n; ++i) {
                let a = unique[i];
                if (a === b) continue;
                let s = a + b + b;
                let cnt = (s%a==0) + (s%b==0);
                if (cnt === 1)
                    ans += count.get(b) * (count.get(b)-1)/2 * count.get(a);
            }
        }
    }
    // All are the same: (a, a, a): always s%a==0, so not possible
    return ans;
};

Problem Description

Given an array of positive integers nums, count the number of triplets (i, j, k) (with i < j < k) such that exactly one of nums[i], nums[j], or nums[k] divides the sum nums[i] + nums[j] + nums[k] with no remainder. In other words, for each triplet, exactly one of the three numbers is a divisor of their sum, and the other two are not. Each element in nums may be used multiple times in different triplets, but a triplet must consist of three distinct indices.

Thought Process

To solve this problem, our first instinct might be to check every possible triplet in the array using three nested loops. For each triplet, we would calculate the sum and check how many of the three numbers divide this sum exactly. If only one does, we count it as a valid triplet. However, this brute-force approach can be very slow, especially if the array is large, since it would require O(n³) time. To optimize, we can use the fact that many numbers may be repeated in the array. By counting the occurrences of each number, we can calculate the number of valid triplets involving those numbers using combinatorics, rather than checking each triplet individually. This shift from examining individual indices to working with unique values and their counts allows us to speed up the solution dramatically.

Solution Approach

The solution involves the following steps:

Count Occurrences: Use a hash map or dictionary to count how many times each unique number appears in nums.
Iterate Over Unique Triplets: Consider all possible combinations of three numbers (a, b, c) where a, b, and c can be the same or different, but represent different indices in the array.
Case Analysis: For each case (all numbers different, two numbers the same, all numbers the same), calculate:
- The sum s = a + b + c.
- How many of a, b, c divide s exactly.
- If exactly one does, count the number of ways to pick such a triplet using the counts from step 1.
Combinatorial Counting: For each valid configuration, multiply the counts accordingly:
- All numbers different: count[a] * count[b] * count[c]
- Two numbers the same: count[a] * (count[a] - 1) / 2 * count[b] (for example, (a, a, b))
- All numbers the same: Not possible, since the sum is always divisible by that number, so it would not satisfy the "exactly one" condition.
Sum Up All Valid Triplets: Add up the number of valid triplets from all cases to get the final answer.

This approach leverages hash maps for O(1) lookups and combinatorial math to avoid redundant computations.

Example Walkthrough

Let's use nums = [2, 3, 4, 6].

First, count occurrences: 2:1, 3:1, 4:1, 6:1 (all unique).
List all triplets:
- (2, 3, 4): sum = 9; 9%2=1, 9%3=0, 9%4=1 → only 3 divides 9 ⇒ valid.
- (2, 3, 6): sum = 11; 11%2=1, 11%3=2, 11%6=5 → none divide.
- (2, 4, 6): sum = 12; 12%2=0, 12%4=0, 12%6=0 → all divide (not valid).
- (3, 4, 6): sum = 13; 13%3=1, 13%4=1, 13%6=1 → none divide.
So only (2, 3, 4) is valid, and since all numbers are unique and appear once, that's 1 valid triplet.
If there were duplicates, e.g., nums = [2, 2, 3, 4], we'd also consider triplets like (2, 2, 3) and use combinatorial counting for repeated numbers.

Time and Space Complexity

Brute-force: O(n³) time, since it checks every possible triplet.
Optimized approach:
- Let m be the number of unique numbers in nums.
- Counting occurrences: O(n).
- Iterating all unique triplets: O(m³) for all-different, O(m²) for two-same, and O(m) for all-same.
- Space: O(m) for the hash map.
This approach is much faster, especially when m is small relative to n.

Summary

The key to solving the Number of Single Divisor Triplets problem efficiently is to shift from examining all possible index triplets to working with unique values and their counts. By using combinatorial math and occurrence maps, we avoid redundant work and count valid triplets directly, leading to an elegant and efficient solution.

AlgoMap.io

Want Help Cracking FAANG?