LeetCode Entry

3116. Kth Smallest Amount With Single Denomination Combination

21.08.2026 hard 2026 kotlin rust

Kth number in multipliers sequence of coins

3116. Kth Smallest Amount With Single Denomination Combination hard substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1458

Problem TLDR

Kth number in multipliers sequence of coins

Intuition

Didn’t solve.

    // 8 12 24
    // 8 16 24
    // 12   24
    //      24
    // how to remove duplicates?
    // i do not see how to apply incl-excl principle
    //

To remove duplicates remove the LCM sequences.

Approach

• the recursive ways is more natural

Complexity

• Time complexity: \(O(log(k)2^n)\)

• Space complexity: \(O(1)\)

Code

    fun findKthSmallest(c: IntArray, k: Int): Long {
        fun gcd(a: Long, b: Long): Long = if (b == 0L) a else gcd(b, a % b)
        fun count(m: Long, i: Int = 0, L: Long = 1): Long = if (i==c.size) 0
        else (c[i] * L / gcd(L, 1L * c[i]))
            .let { nL -> count(m, i + 1, L) + m / nL - count(m, i + 1, nL) }
        var lo = 1L; var hi = 1L * c.min() * k
        while (lo <= hi) {
            val m = (lo + hi) / 2
            if (count(m) < k) lo = m + 1 else hi = m - 1
        }
        return lo
    }