We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Single Divisor Triplets

Number: 1383

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Given an array of positive integers, count the number of ordered triplets (i, j, k) of distinct indices such that the sum of the three elements is divisible by exactly one of the three numbers. Note that even if the array contains duplicate numbers, the triplets must use three distinct indices. The answer should count all orderings (i.e. permutations) of a valid combination.

Key Insights

  • The values in nums are bounded by 100 while the array length can be up to 10^5. This allows us to use a frequency table and iterate over possible values (1 to 100) instead of iterating over indices directly.
  • For each combination of numbers (a, b, c) from the frequency table, compute the sum (S = a + b + c) and check if S is divisible by exactly one of a, b, or c.
  • When counting triplets, careful handling is required for cases where the selected numbers are distinct, two are equal, or all three are equal. Since the problem asks for ordered triplets, every unordered selection of 3 distinct indices converts to 6 ordered triplets.
  • Using combinatorics (e.g. freq choose 2, freq choose 3) for duplicates and then multiplying by 6 (or the appropriate factor) gives the correct count.

Space and Time Complexity

Time Complexity: O(100^3) which is O(1e6) operations in the worst case (negligible compared to 10^5).
Space Complexity: O(101) or O(1) extra space for the frequency table.

Solution

The solution uses a frequency array of size 101 (since nums[i] is in [1, 100]) to count occurrences. Then, by iterating over all triple combinations (a, b, c) with a ≤ b ≤ c, we check if the sum S = a + b + c is divisible by exactly one of a, b, or c.
For each valid combination, we calculate the number of unordered ways to pick indices based on the frequency counts:

  • All numbers distinct: ways = freq[a] * freq[b] * freq[c]
  • Two identical and one different: ways = C(freq[x], 2) * freq[y] (where x is the repeated number)
  • All equal: ways = C(freq[a], 3)
    Since every unordered triplet of indices gives rise to 6 ordered triplets, we multiply the computed ways by 6 and add it to the answer.

Code Solutions

# Python solution

def singleDivisorTriplets(nums):
    # Build frequency table for numbers 1 to 100.
    freq = [0] * 101
    for num in nums:
        freq[num] += 1

    # Helper functions for combination counts.
    def comb2(n):
        # returns n choose 2
        return n * (n - 1) // 2

    def comb3(n):
        # returns n choose 3
        return n * (n - 1) * (n - 2) // 6

    answer = 0
    # Iterate over all combinations of possible values.
    for a in range(1, 101):
        if freq[a] == 0:
            continue
        for b in range(a, 101):
            if freq[b] == 0:
                continue
            for c in range(b, 101):
                if freq[c] == 0:
                    continue
                total = a + b + c
                # Check divisibility for each number.
                countDiv = 0
                if total % a == 0:
                    countDiv += 1
                if total % b == 0:
                    countDiv += 1
                if total % c == 0:
                    countDiv += 1

                # Only consider if exactly one divisor satisfies the condition.
                if countDiv != 1:
                    continue

                # Count the number of ways to choose indices with these values.
                if a == b and b == c:
                    # All three numbers are equal.
                    if freq[a] >= 3:
                        ways = comb3(freq[a])
                    else:
                        ways = 0
                elif a == b and b != c:
                    # a and b are the same, c is different.
                    if freq[a] >= 2:
                        ways = comb2(freq[a]) * freq[c]
                    else:
                        ways = 0
                elif a != b and b == c:
                    # b and c are the same, a is different.
                    if freq[b] >= 2:
                        ways = freq[a] * comb2(freq[b])
                    else:
                        ways = 0
                else:
                    # All numbers are distinct.
                    ways = freq[a] * freq[b] * freq[c]

                # Multiply by 6 because order matters.
                answer += ways * 6

    return answer

# Example usage:
print(singleDivisorTriplets([4,6,7,3,2]))  # Expected output: 12
print(singleDivisorTriplets([1,2,2]))      # Expected output: 6
print(singleDivisorTriplets([1,1,1]))      # Expected output: 0
← Back to All Questions