3116. Kth Smallest Amount With Single Denomination Combination

Array Math Binary Search Number Theory combinatorics

Problem Overview

Each coin only produces its own multiples - you never mix denominations.

Intuition

Each coin only produces its own multiples - you never mix denominations. So the valid amounts are just the union of those arithmetic sequences. k can be up to 2e9, so you cannot generate them. Instead binary search the answer x and ask: how many distinct valid amounts are <= x? That count is monotonic, so the smallest x with count >= k is the answer.

Algorithm

1Precompute every non-empty coin subset: take its LCM, and store it with a + sign if the subset size is odd, - if even (inclusion-exclusion).
2Binary search lo=1, hi=k*min(coins). For mid, count = sum over signed LCMs of mid/lcm (skip when lcm > mid).
3If count >= k, try smaller (hi = mid); else lo = mid + 1.
4Return lo.

Example Walkthrough

Input: coins = [3, 6, 9], k = 3

1.Valid amounts in order: 3, 6, 9, 12, 15, ...
2.At x = 9, multiples of 3 give 3, of 6 give 1, of 9 give 1; subtract overlaps via LCM so the distinct count is 3.
3.So the 3rd amount is 9.

Output: 9

Common Pitfalls

•A plain sum of floor(x/coin) double-counts shared multiples - you need inclusion-exclusion on LCMs.
•Compute LCM as a/gcd*b to avoid overflowing a*b.
•n is at most 15, so 2^n subsets are fine; k is huge, so heap generation will not work.
•hi = k * min(coins) is a safe upper bound because the smallest coin alone already covers k multiples by then.

3116.cs

// Approach: Binary search the answer x. Count how many distinct amounts <= mid
// via inclusion-exclusion over coin-subset LCMs (add odd subsets, subtract even).
// Precompute each subset's LCM once with a +/- sign.
// Complexity: O(2^n * n + 2^n * log(k * minCoin)) time, O(2^n) space.
public class Solution
{
    public long FindKthSmallest(int[] coins, int k)
    {
        long[] signedLcms = BuildSignedLcms(coins);
        long lo = 1;
        long hi = (long)k * coins.Min();

        while (lo < hi)
        {
            long mid = lo + (hi - lo) / 2;
            if (CountUpTo(signedLcms, mid) >= k)
                hi = mid;
            else
                lo = mid + 1;
        }

        return lo;
    }

    private long CountUpTo(long[] signedLcms, long m)
    {
        long res = 0;
        foreach (long signed in signedLcms)
        {
            long lcm = Math.Abs(signed);
            if (lcm > m)
                continue;
            res += m / lcm * Math.Sign(signed);
        }
        return res;
    }

    private long[] BuildSignedLcms(int[] coins)
    {
        int n = coins.Length;
        int maxMask = 1 << n;
        var list = new List<long>(maxMask - 1);

        for (int mask = 1; mask < maxMask; mask++)
        {
            long lcm = 1;
            int bits = 0;
            for (int i = 0; i < n; i++)
            {
                if ((mask & (1 << i)) == 0)
                    continue;
                bits++;
                lcm = Lcm(lcm, coins[i]);
            }
            list.Add((bits & 1) == 1 ? lcm : -lcm);
        }

        return list.ToArray();
    }

    private long Lcm(long a, long b) => a / Gcd(a, b) * b;

    private long Gcd(long a, long b)
    {
        while (b != 0)
        {
            long t = a % b;
            a = b;
            b = t;
        }
        return a;
    }
}

Was this solution helpful?