Author: Aryan KD
Tester: Aryan KD
Editorialist: Aryan KD
DIFFICULTY:
CAKEWALK, SIMPLE, EASY.
PREREQUISITES:
Math .
PROBLEM:
Program accept two integer N and M . where N equals to number of bits and M equals to number of set bits. implement the program to find the sum of all number possible from N bits having the count of set bits equal to M .
EXPLANATION:
we have given two numbers N and M where N = number of bits and M= number of set bits
lets take a example n=3 and m=2
first we have to find all possible 3 bits numbers
that is
000 =0
001=1
010=2
011=3
100=4
101=5
110=6
111=7
now in that we have to find number of set bits equal to 2 (here M=2 )
here number of set bit=2 numbers’s are 3, 5, 6 and addition of these numbers are 14 so the output is 14
in this question we have to take array and scan it and we have to find which numbers set bit equal to M and latter we have to add all these numbers.
SOLUTIONS:
Setter's Solution
//bit setting
#include <bits/stdc++.h>
using namespace std;
void testcase()
{
int n, m, k, sum = 0;
cin >> n >> m;
for (int i = 0; i < pow(2, n); i++)
{
int count = 0;
k = i;
while (k > 0)
{
if (k & 1 == 1)
{
count++;
}
k = k >> 1;
}
if (count == m)
{
sum += i;
}
}
cout << sum;
}
int main()
{
int t;
cin >> t;
while (t–)
{
testcase();
cout << endl;
}
return 0;
}
Tester's Solution
//bit setting
#include <bits/stdc++.h>
using namespace std;
void testcase()
{
int n, m, k, sum = 0;
cin >> n >> m;
for (int i = 0; i < pow(2, n); i++)
{
int count = 0;
k = i;
while (k > 0)
{
if (k & 1 == 1)
{
count++;
}
k = k >> 1;
}
if (count == m)
{
sum += i;
}
}
cout << sum;
}
int main()
{
int t;
cin >> t;
while (t–)
{
testcase();
cout << endl;
}
return 0;
}
Editorialist's Solution
//bit setting
#include <bits/stdc++.h>
using namespace std;
void testcase()
{
int n, m, k, sum = 0;
cin >> n >> m;
for (int i = 0; i < pow(2, n); i++)
{
int count = 0;
k = i;
while (k > 0)
{
if (k & 1 == 1)
{
count++;
}
k = k >> 1;
}
if (count == m)
{
sum += i;
}
}
cout << sum;
}
int main()
{
int t;
cin >> t;
while (t–)
{
testcase();
cout << endl;
}
return 0;
}