Problem description
Mr. Binary is lost and wants to be found but the problem is he understands only binary. His house is located at a maximum binary equivalence possible, from the given set of numbers. A set is a binary equivalence if the number of 0 zeros and ones from a set of number are equal.
Constraints
1 <= N <= 20
1 <= Arr[i] <= 10^5, where Arr[i] is the ith element in the set of N numbers in second line of input
Arr[i] will be unique
Input
First line contains N denoting the number of decimal numbers
Next line contains N space separated decimal numbers
Output
Single line output printing possible binary equivalence where number of digits in this number is equal to number of bits present in the largest element in second line of input. If there is no set which has binary equivalence then return 0 padded to number of bits present in the largest element in second line of input.
Time Limit
1
Examples
Example 1
Input
3
2 7 10
Output
0011
Editorial :::::
i will put code first so that if you understand from it then its ok otherwise approach to solve is at end is at the end.
#include <bits.stdc++.h>
using namespace std;
#define l long long
int total = 0;
typedef struct in_item {
int one,zero ,len;
}item;
void convertbinary(int n , int lent)
{
int b[32] ={0};
int i = 0;
while (n > 0) {
b[i] = n % 2;
n = n / 2;
i++;
}
for (int j = lent-1; j >= 0; j--)
cout << b[j];
}
item build(int one ,int zero , int len)
{
item x = {one, zero , len};
return x;
}
item calculate_binary(int mx , int lent)
{
int con1=0 ,con0=0 , con_len=0;
while(mx>0)
{
if(mx&1 == 1)
{
con1++;
}
else
{
con0++;
}
mx /=2;
con_len++;
}
con0 += lent - con_len;
return build(con1,con0 ,con_len);
}
item calculate_len(int mx)
{
int con1=0 ,con0=0 , con_len=0;
while(mx>0)
{
if(mx&1 == 1)
{
con1++;
}
else
{
con0++;
}
mx /=2;
con_len++;
}
return build(con1,con0 ,con_len);
}
void subset_find(int arr[],int n , item *store)
{
total =0;
int count1 = pow(2,n);
for (int i = 0; i < count1; i++)
{
int tone=0 , tzero=0 ;
for (int j = 0; j < n; j++)
{
if ((i & (1 << j)) > 0)
{
int x = arr[j];
tone += store[x].one;
tzero += store[x].zero;
}
}
if(tzero == tone && tone>0)
{
total++;
}
}
}
int main()
{
int n;
cin>>n;
int a[n];
int mx = INT_MIN;
for(int i=0;i<n;i++)
{
cin>>a[i];
mx = max(a[i],mx);
}
//find binary
item mx_len = calculate_len(mx);
//cout<<mx_len.one<<" "<<mx_len.zero<<" "<<mx_len.len<<endl;
int lent = mx_len.len;
item store[n];
int elem[n];
for(int i=0;i<n;i++)
{elem[i] = i;
store[i] = calculate_binary(a[i] , lent);
}
//for(int i=0;i<n;i++)
//{
// cout<<store[i].one<<" "<<store[i].zero<<" "<<store[i].len<<endl;
//}
//find subset
subset_find(elem,n , store);
convertbinary(total, lent);
}
// now the approach to solve it
as you see that whole problem move around bits.
so i have first find the max element and find ones and zero in it and then most important its length so after that i made a array of structure as you see on top of the code and store the length , ones ,zeros of every element index wise now important point is when you calculating and storing ones and zero in struct of array than if the length of binary representation of a number is less then the max element binary representation then add the diff of length in number of zeros.
so now only thing left is to find the subset of main set that have same number of zeros and ones.
at last we find all subset of that set and and calculate the number of zero and one by adding them as we have stored them in array of struct.
after counting number of subset have equivalence now answer is to represent the number in binary and of length equal to max element binary representation length
ask if you have any query.