An amount is reachable when it is a multiple of at least one coin, so the k-th smallest reachable value is monotone in a counting function: how many valid amounts sit at or below a given `x`. That monotonicity is what lets me binary-search the answer instead of enumerating multiples one by one. Counting valid amounts up to `x` is a union-of-multiples problem. The count of multiples of `c` not exceeding `x` is `x/c`, but summing that over every coin double-counts anything divisible by two coins at once. Inclusion-exclusion over coin subsets repairs it: add `x/lcm(S)` for odd-sized subsets, subtract it for even-sized ones. ## Key idea With `coins.length` at most 15, I can afford all `2^n - 1` non-empty subsets. For each subset I precompute its lcm and its sign once, before the search. The count of valid amounts at or below `x` is then a single pass: the sum of `sign[S] * (x/lcm[S])`. I binary-search the smallest `x` with `count(x) >= k`; the upper bound `k * 25` holds because every coin is at most 25, so the k-th reachable value can be no larger. The brute force I rejected was a min-heap of multiples, popping the next smallest k times. With `k` as large as `2*10^9` that never finishes, while counting plus binary search runs in `O(2^n log(answer))` and does. ### Worked example Take `coins = [5, 2]`, `k = 7`. The subsets are `{5}` (lcm 5, sign +), `{2}` (lcm 2, sign +), and `{5,2}` (lcm 10, sign -). For `x = 12` the count is `12/5 + 12/2 - 12/10 = 2 + 6 - 1 = 7`; for `x = 11` it is `2 + 5 - 1 = 6`. So 12 is the first value whose count reaches 7, matching the reachable list 2, 4, 5, 6, 8, 10, 12. ### Complexity Time: `O(2^n log(k*25))` — the subset table is built once in `O(n * 2^n)`, and each of the `O(log answer)` search steps scans all subsets. Space: `O(2^n)` for the stored lcms and signs. ### Code (C++) ```cpp class Solution { public: long long findKthSmallest(vector& coins, int k) { int n = coins.size(); vector lcms; vector signs; long long CAP = (long long)k * 25 + 5; for (int mask = 1; mask < (1< CAP) { ovf = true; break; } } if (ovf) continue; lcms.push_back(l); signs.push_back((bits & 1) ? 1 : -1); } auto cnt = [&](long long x){ long long c=0; for(size_t i=0;i= k) hi = mid; else lo = mid+1; } return lo; } }; ``` ### One note Compute the lcm as `l / gcd(l, c) * c`, never `l * c / gcd`: the intermediate product can overflow a 64-bit integer even when the final lcm is small. I also cap the running lcm at `k*25` and drop any subset that exceeds it, since a divisor beyond the search bound contributes `x/lcm = 0` to every count and only risks overflow.