# Maximum Product(https://www.codechef.com/CBST2021/problems/SHOP04)

Practice

Author: noob_tech
Tester: noob_tech
Editorialist: noob_tech

# DIFFICULTY:

CAKEWALK, SIMPLE, EASY.

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