CIELRCPT: Ciel and Receipt

CIELRCPT: Ciel and Receipt

Link for the problem: CIELRCPT

SOLUTION:

We have total price P. To buy min number of menu, we would start buying menu with maximum price if possible. So  we would always make this as our greedy choice.

CODE:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a[12],i,j,k;
    for(i=0;i<12;i++)
    {
        a[i]=pow(2,i);
    }
   int t;
   cin>>t;
   while(t--)
   {
       int n,s=0;
       cin>>n;
       for(i=11;i>=0;i--)
       {
          s+=(n/a[i]);
          n=n%a[i];
       }
       printf("%d\n",s);
   }
    return 0;

}