Untitled

// AMAN JAIN MCA 1st YEAR 2nd SEM

// time O(N), space O(1)
// Approach: Basic greedy
class Solution{
public:

    vector<int> minPartition(int N) {
        vector<int> ans;
        vector<int> coins = {2000, 500, 200, 100, 50, 20, 10, 5, 2, 1};
        while(N) {
            for(int i = 0; i < coins.size(); ++i) {
                if(N >= coins[i]) {
                    N = N - coins[i];
                    ans.push_back(coins[i]);
                    break;
                }
            }
        }
        return ans;
    }
};