Minimum Number of Coins(Greedy)

Image Copyright: pymnts.com

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

#include<bits/stdc++.h> #define MX 1000007 #define ll long long #define ull unsigned long long #define fori(a,n) for(int i=a;i<n;i++) #define forj(a,n) for(int j=0;j<n;j++) using namespace std; struct node { int x,y; }; int main() { vector<node>trace; int n,v,total=0; cin>>n>>v; int coins[n],no_co[n]; for(int i=0;i<n;i++) cin>>coins[i]; sort(coins,coins+n,greater<int>()); for(int i=0;i<n;i++){ if(v>=coins[i]){ int a=v/coins[i]; total+=a; v%=coins[i]; trace.push_back({coins[i],a}); } } cout<<total<<endl; for(int i=0;i<trace.size();i++) cout<<trace[i].x<<"---"<<trace[i].y<<endl; cout<<endl; return 0; }