825. The kth Amount You Can Make

A machine accepts m coin types, of values d[0] ... d[m-1]. It refuses mixed payments: a purchase must be paid with a pile of IDENTICAL coins. So an amount is payable exactly when it is a positive multiple of at least one of the coin values.

Write the payable amounts out in increasing order, with no repeats, and print the kth of them, counting from 1.

coins 3 6 9, k = 3 -> 9 payable: 3, 6, 9, 12, 15, 18 coins 5 2, k = 7 -> 12 payable: 2, 4, 5, 6, 8, 10, 12 coins 7 11 13, k = 1 -> 7

## Counting is easy, listing is not

k can be 2 * 10^9, so the amounts cannot be generated one at a time. But the number of payable amounts at or below a given v has a closed form, and once a quantity can be COUNTED cheaply, the kth of it can be found by binary search. That inversion is the whole method.

## The count, by inclusion and exclusion

Multiples of a single coin d up to v number v / d. Adding those counts over all coins double counts every amount payable by two different coins, and an amount divisible by both d[i] and d[j] is exactly a multiple of their least common multiple. Alternate the signs:

count(v) = sum over every non-empty subset S of the coins (-1)^(|S| + 1) * (v / lcm(S))

With m at most 15 there are 32767 subsets. Precompute each subset's least common multiple once, using lcm(x, y) = x / gcd(x, y) * y and DIVIDING BEFORE MULTIPLYING, and drop any subset whose least common multiple already exceeds the top of the search range, since v / lcm is 0 for every v you will ever ask about. That precomputation turns each count into a single pass over a short list.

## What the neighbouring problems in the bank do differently

Problem 784 is this question with exactly two coins. Two coins need no general machinery: one lcm and three terms. Problem 785 counts the integers divisible by NONE of a set of primes, which is the complement of this count, and its inputs are guaranteed pairwise coprime, so every subset lcm is just a product and nothing can collide.

Here the coin values are arbitrary. 4 and 6 have lcm 12 rather than 24, 3 and 9 have lcm 9, and a duplicate coin value has lcm equal to itself. Computing the lcm properly, rather than multiplying, is the part those two problems never have to face.

## Why the predicate is monotone

count(v) is a sum of terms v / lcm, each non-decreasing in v, so count is non-decreasing. Therefore count(v) >= k is false and then true, and the first v at which it turns true is the kth payable amount. It must be payable: count only rises at payable amounts, so the first v reaching k is one where the count rose.

## The bounds

lo = 1.

hi = min(d) * k. The smallest coin alone supplies k distinct payable amounts by then, so the count at hi is at least k and the answer cannot be larger.

## Why the loop terminates

mid = lo + (hi - lo) / 2 with lo <= mid < hi shrinks the range every iteration, so about 36 steps for a range of 5 * 10^10.

## Overflow

hi reaches 25 * 2 * 10^9 = 5 * 10^10, which needs 64 bits before the search starts. The least common multiple of a subset can climb far higher; capping it against hi as you build the table keeps every stored value inside 64 bits and keeps the counting loop short.

## Cost

Time O(2^m * m + 2^m log(min(d) * k)). Space O(2^m).

Constraints - `1 ≤ m ≤ 15` - `1 ≤ d[i] ≤ 25` - `1 ≤ k ≤ 2000000000`