*Author:* noob_tech

*Tester:* noob_tech

*Editorialist:* noob_tech

# DIFFICULTY:

CAKEWALK, SIMPLE, EASY.

# PREREQUISITES:

Math .

# PROBLEM:

CodeMaster has gone for the shopping with M Rupees.He wants to buy the maximum number of products with given M Rupees.

After reaching the store,The Shopkeeper gave him N numbers of products list.Each ith product represents the Price of that product.

CodeMaster decided that he will buy only those products whose price is the power of two.

NOTE- CodeMaster can buy only one product of the same price.

Help the code master to buy the maximum number of products and print count of the maximum number of products.

# EXPLANATION:

We are given M rupees and an array of size N where each element of an array contains price of each product.

We have to find that how many product we can buy with given M rupees.

But we can buy only those product whose is in the power of two.

Note- We can buy only one product of same price and finally print how many product we bought.

Consider we are given total number of product(N) is 5 with product price is { 4,1 ,2 ,7 ,8 } and Total rupees M is 10.

First he will buy 2nd number of product which price is 1 and it is also in power of 2. Now CodeMaster has only 9 Rupees remaining and total_count of maximum number of product is 1.

Next he will 3rd number of product whose price is 2 and two is also in power of 2. Now CodeMaster has only 7 Rupees remaining and total_count of maximum number of product is 2.

Next he will 1st number of product whose price is 4 and 4 is also in power of 2. Now CodeMaster has only 3 Rupees remaining and total_count of maximum number of product is 3. Now he will try buy those product whose price is 8 and he has only 3 rupees so can’t buy.

we can buy total_count of maximum number of product 3. So output will be 3.

# SOLUTIONS:

## Setter's Solution

#include<bits/stdc++.h>

using namespace std;

int main()

{

int t;

cin >> t;

while (t–)

{

int n, m;

cin >> n >> m;

int a[n];

for (int i = 0; i < n; i++)

{

cin >> a[i];

}

sort(a, a + n);

int cnt = 0;

for (int i = 0; i < n; i++)

{

int x = (ceil(log2(a[i])) == floor(log2(a[i])));

if (x)

{

if (a[i] <= m)

{

cnt++;

m = m - a[i];

}

else

{

break;

}

}

}

cout << cnt << endl;

}

return 0;

}

## Tester's Solution

#include<bits/stdc++.h>

using namespace std;

int main()

{

int t;

cin >> t;

while (t–)

{

int n, m;

cin >> n >> m;

int a[n];

for (int i = 0; i < n; i++)

{

cin >> a[i];

}

sort(a, a + n);

int cnt = 0;

for (int i = 0; i < n; i++)

{

int x = (ceil(log2(a[i])) == floor(log2(a[i])));

if (x)

{

if (a[i] <= m)

{

cnt++;

m = m - a[i];

}

else

{

break;

}

}

}

cout << cnt << endl;

}

return 0;

}

## Editorialist's Solution

#include<bits/stdc++.h>

using namespace std;

int main()

{

int t;

cin >> t;

while (t–)

{

int n, m;

cin >> n >> m;

int a[n];

for (int i = 0; i < n; i++)

{

cin >> a[i];

}

sort(a, a + n);

int cnt = 0;

for (int i = 0; i < n; i++)

{

int x = (ceil(log2(a[i])) == floor(log2(a[i])));

if (x)

{

if (a[i] <= m)

{

cnt++;

m = m - a[i];

}

else

{

break;

}

}

}

cout << cnt << endl;

}

return 0;

}