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;
}