2952. Minimum Number of Coins to be Added Medium

1/**
2 * [2952] Minimum Number of Coins to be Added
3 *
4 * You are given a 0-indexed integer array coins, representing the values of the coins available, and an integer target.
5 * An integer x is obtainable if there exists a subsequence of coins that sums to x.
6 * Return the minimum number of coins of any value that need to be added to the array so that every integer in the range [1, target] is obtainable.
7 * A subsequence of an array is a new non-empty array that is formed from the original array by deleting some (possibly none) of the elements without disturbing the relative positions of the remaining elements.
8 *  
9 * <strong class="example">Example 1:
10 * 
11 * Input: coins = [1,4,10], target = 19
12 * Output: 2
13 * Explanation: We need to add coins 2 and 8. The resulting array will be [1,2,4,8,10].
14 * It can be shown that all integers from 1 to 19 are obtainable from the resulting array, and that 2 is the minimum number of coins that need to be added to the array. 
15 * 
16 * <strong class="example">Example 2:
17 * 
18 * Input: coins = [1,4,10,5,7,19], target = 19
19 * Output: 1
20 * Explanation: We only need to add the coin 2. The resulting array will be [1,2,4,5,7,10,19].
21 * It can be shown that all integers from 1 to 19 are obtainable from the resulting array, and that 1 is the minimum number of coins that need to be added to the array. 
22 * 
23 * <strong class="example">Example 3:
24 * 
25 * Input: coins = [1,1,1], target = 20
26 * Output: 3
27 * Explanation: We need to add coins 4, 8, and 16. The resulting array will be [1,1,1,4,8,16].
28 * It can be shown that all integers from 1 to 20 are obtainable from the resulting array, and that 3 is the minimum number of coins that need to be added to the array.
29 * 
30 *  
31 * Constraints:
32 * 
33 * 	1 <= target <= 10^5
34 * 	1 <= coins.length <= 10^5
35 * 	1 <= coins[i] <= target
36 * 
37 */
38pub struct Solution {}
39
40// problem: https://leetcode.com/problems/minimum-number-of-coins-to-be-added/
41// discuss: https://leetcode.com/problems/minimum-number-of-coins-to-be-added/discuss/?currentPage=1&orderBy=most_votes&query=
42
43// submission codes start here
44
45impl Solution {
46    pub fn minimum_added_coins(coins: Vec<i32>, target: i32) -> i32 {
47        0
48    }
49}
50
51// submission codes end
52
53#[cfg(test)]
54mod tests {
55    use super::*;
56
57    #[test]
58    fn test_2952() {
59    }
60}
61