Ciel and Receipt Solution

Problem
Tomya is a girl. She loves Chef Ciel very much. Tomya like a positive integer p, and now she wants to get a receipt of Ciel’s restaurant whose total price is exactly p.
Note that the i-th menu has the price 2^i-1 (1 ≤ i ≤ 12). Find the minimum number of menus whose total price is exactly p.

CodeChef Problem Link

Input

The first line contains an integer T, the number of test cases. Then T test cases follow. Each test case contains an integer p.

Output

For each test case, print the minimum number of menus whose total price is exactly p.

Sample Input

1
10

Sample Output

2

Explanation

In the first sample, examples of the menus whose total price is 10 are the following:
1+1+1+1+1+1+1+1+1+1 = 10 (10 menus)
1+1+1+1+1+1+1+1+2 = 10 (9 menus)
2+2+2+2+2 = 10 (5 menus)
2+4+4 = 10 (3 menus)
2+8 = 10 (2 menus)
Here the minimum number of menus is 2.

Solution

Code Implementation

#include <iostream>
#include<math.h>
using namespace std;

int main() {
    int T, ans, p;
    cin>>T;

    while(T>0) {
        ans=0;
        cin>>p;

        for(int k=11; k>=0; k--) {
            int c = pow(2,k);

            //Subtracting multiples of 2 (2^i), starting from greatest to least
            // to find the minimum number of menus
            while(p-c>=0) {
                p = p-c;
                ans++;
            }

        }

        T--;

        cout<<ans<<endl;
    }

    return 0;
}