#include<stdcpp.h>
using namespace std;
class Solution {
public:
    int minimumAddedCoins(vector<int>& coins, int target) {
        const int len = coins.size(); 
        sort(coins.begin(), coins.end());
        int express = 0;
        int idx = 0;
        int ans = 0;
        while(express < target){
            if(idx < len && express+1 >= coins[idx]){
                express += coins[idx++];
            }else{
                ans++;
                express += express + 1;
            }
        }
        cout<<ans<<endl;
        return ans;
    }
};
int main(){
    Solution sol;

    vector<int> ex1 = {1,4,10};
    int target1 = 19;
    sol.minimumAddedCoins(ex1,target1);

    vector<int> ex2 = {1,4,10,5,7,19};
    int target2 = 19;
    sol.minimumAddedCoins(ex2,target2);

    vector<int> ex3 = {1,1,1};
    int target3 = 20;
    sol.minimumAddedCoins(ex3,target3);

    vector<int> ex4 = {1};
    int target4 = 100000;
    sol.minimumAddedCoins(ex4,target4);
    return 0;
}