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

Kth Smallest Amount With Single Denomination Combination

Number: 3375

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given an array of distinct coin denominations, you have an infinite number of coins for each denomination. However, you are not allowed to combine coins of different denominations. For each coin, you can only form amounts that are integer multiples of its value. Return the kth smallest distinct amount that can be formed by using exactly one coin denomination.

Key Insights

  • Each coin with denomination d generates a sorted list of multiples: d, 2d, 3d,….
  • The union of these lists is sorted, but common multiples (e.g., amounts like 10 coming from different coins) appear only once.
  • A direct enumeration is inefficient due to the high bound of k (up to 2×10⁹). Instead, use binary search to guess an amount X, and then count how many distinct multiples across all coins do not exceed X.
  • Use inclusion–exclusion principle to correctly count the distinct numbers (i.e. the union) without overcounting overlaps between multiples from different coins.

Space and Time Complexity

Time Complexity: O(2^n * log(maxAnswer)), where n is the number of coins (n ≤ 15) and maxAnswer is the search space (≈ k * min(coins)). Space Complexity: O(2^n) in the worst-case scenario if storing subsets; however, by doing recursion on the fly, additional space can be kept minimal.

Solution

We solve the problem with a binary search over the candidate amount X. For a given X, we count the number of distinct amounts that can be formed (i.e. numbers which are multiples of at least one coin) and are ≤ X using inclusion–exclusion. The inclusion–exclusion formula iterates over every non-empty subset of coins, computes the LCM for that subset, and uses floor(X / LCM) with an alternating sign based on the parity of the subset’s length. Finally, we find the smallest X such that the union count is at least k.

The helper function (count) calculates the number of distinct multiples up to X. Then binary search is performed within the range [1, (min(coins)*k)].

Key data structures and techniques:

  • Binary search for finding kth smallest amount.
  • Recursion/bitmask to iterate over subsets for applying inclusion–exclusion.
  • LCM calculation using GCD from number theory.

Code Solutions

import math

def kthSmallestAmount(coins, k):
    # Helper to compute the Least Common Multiple (LCM) of two numbers
    def lcm(a, b):
        return a * b // math.gcd(a, b)
    
    n = len(coins)
    
    # Inclusion-exclusion count: counts how many distinct multiples <= x using the coins
    def count(x):
        total = 0
        # iterate over all non-empty subsets using bit masks (range 1 to (1<<n)-1)
        for mask in range(1, 1 << n):
            current_lcm = 1
            bits = 0
            valid = True
            for i in range(n):
                if mask & (1 << i):
                    bits += 1
                    current_lcm = lcm(current_lcm, coins[i])
                    # if lcm exceeds x, further division would yield 0
                    if current_lcm > x:
                        valid = False
                        break
            if valid:
                # add or subtract count based on parity of bits in the subset
                if bits % 2 == 1:
                    total += x // current_lcm
                else:
                    total -= x // current_lcm
        return total

    low, high = 1, min(coins) * k
    while low < high:
        mid = (low + high) // 2
        if count(mid) < k:
            low = mid + 1
        else:
            high = mid
    return low

# Example usage:
print(kthSmallestAmount([3, 6, 9], 3))  # Expected output: 9
print(kthSmallestAmount([5, 2], 7))     # Expected output: 12
← Back to All Questions