LeetCode 3116 (Hard) — binary search + inclusion-exclusion makes it easy

Full walkthrough: https://www.youtube.com/watch?v=vFuFA3ByCs0

LeetCode 3116 — Kth Smallest Amount With Single Denomination Combination. Here’s the trick everyone misses:

Brute force (generate all multiples, pick k-th) fails because k can reach 2×10⁹.

The real approach:

Binary search the answer X
Count valid amounts ≤ X using inclusion-exclusion
Odd subsets add, even subtract (bitmask over coins)
LCM via GCD, break when LCM > X
O(n · 2ⁿ · log(k·M)) — passes cleanly.

The 26% acceptance rate makes this look harder than it is. Once you see the count(X) monotonic trick, it clicks.