3116. Kth Smallest Amount With Single Denomination Combination Hard

1/**
2 * [3116] Kth Smallest Amount With Single Denomination Combination
3 *
4 * You are given an integer array coins representing coins of different denominations and an integer k.
5 * You have an infinite number of coins of each denomination. However, you are not allowed to combine coins of different denominations.
6 * Return the k^th smallest amount that can be made using these coins.
7 *  
8 * <strong class="example">Example 1:
9 * <div class="example-block" style="
10 *     border-color: var(--border-tertiary);
11 *     border-left-width: 2px;
12 *     color: var(--text-secondary);
13 *     font-size: .875rem;
14 *     margin-bottom: 1rem;
15 *     margin-top: 1rem;
16 *     overflow: visible;
17 *     padding-left: 1rem;
18 * ">
19 * Input: <span class="example-io" style="
20 *     font-family: Menlo,sans-serif;
21 *     font-size: 0.85rem;
22 * ">coins = [3,6,9], k = 3</span>
23 * Output: <span class="example-io" style="
24 *     font-family: Menlo,sans-serif;
25 *     font-size: 0.85rem;
26 * "> 9</span>
27 * Explanation: The given coins can make the following amounts:<br />
28 * Coin 3 produces multiples of 3: 3, 6, 9, 12, 15, etc.<br />
29 * Coin 6 produces multiples of 6: 6, 12, 18, 24, etc.<br />
30 * Coin 9 produces multiples of 9: 9, 18, 27, 36, etc.<br />
31 * All of the coins combined produce: 3, 6, <u>9</u>, 12, 15, etc.
32 * </div>
33 * <strong class="example">Example 2:
34 * <div class="example-block" style="
35 *     border-color: var(--border-tertiary);
36 *     border-left-width: 2px;
37 *     color: var(--text-secondary);
38 *     font-size: .875rem;
39 *     margin-bottom: 1rem;
40 *     margin-top: 1rem;
41 *     overflow: visible;
42 *     padding-left: 1rem;
43 * ">
44 * Input:<span class="example-io" style="
45 *     font-family: Menlo,sans-serif;
46 *     font-size: 0.85rem;
47 * "> coins = [5,2], k = 7</span>
48 * Output:<span class="example-io" style="
49 *     font-family: Menlo,sans-serif;
50 *     font-size: 0.85rem;
51 * "> 12 </span>
52 * Explanation: The given coins can make the following amounts:<br />
53 * Coin 5 produces multiples of 5: 5, 10, 15, 20, etc.<br />
54 * Coin 2 produces multiples of 2: 2, 4, 6, 8, 10, 12, etc.<br />
55 * All of the coins combined produce: 2, 4, 5, 6, 8, 10, <u>12</u>, 14, 15, etc.
56 * </div>
57 *  
58 * Constraints:
59 * 
60 * 	1 <= coins.length <= 15
61 * 	1 <= coins[i] <= 25
62 * 	1 <= k <= 2 * 10^9
63 * 	coins contains pairwise distinct integers.
64 * 
65 */
66pub struct Solution {}
67
68// problem: https://leetcode.com/problems/kth-smallest-amount-with-single-denomination-combination/
69// discuss: https://leetcode.com/problems/kth-smallest-amount-with-single-denomination-combination/discuss/?currentPage=1&orderBy=most_votes&query=
70
71// submission codes start here
72
73impl Solution {
74    pub fn find_kth_smallest(coins: Vec<i32>, k: i32) -> i64 {
75        
76    }
77}
78
79// submission codes end
80
81#[cfg(test)]
82mod tests {
83    use super::*;
84
85    #[test]
86    fn test_3116() {
87    }
88}
89