[Solved] Binary Equivalent TCS CodeVita season9 Zone 2 Problem With Solution

 Binary Equivalent

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 the 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

Explanation

2 -> 0010 - 1's = 1, 0's = 3

7 -> 0111 - 1's = 3, 0's = 1

10 -> 1010 - 1's = 2, 0's = 2

Here we have taken up to 4 bits because the maximum number is 10 which needs 4 bits to be represented in binary. The number of zeroes and ones across the set is, 6 each. Hence, the set of [2,7,10] has binary equivalence. Similarly, if you consider set[2,7], it also has binary equivalence, 4 each. But set [7,10] does not have binary equivalence. Likewise, set[10] has binary equivalence of 2 each.

Total number of unique sets where binary equivalence is possible from all combinations are 3 viz. Sets are [2,7,10], [2,7] and [10] which is the final answer. But as Mr. Binary only understands zeroes and ones, return the binary of 3.

Since 10 is the largest element in the input on line 2, the number of bits required to represent 10 in binary is 4. Hence output needs to be padded upto 4 digits. Since binary of 3 represented as a 4-digit number is 0011, the answer is 0011

Note

Do not consider empty subset

Example 2

Input

1

7

Output

000

Explanation

7 -> 111 - 1's = 3, 0's = 1

Since there is only one element in the set and it also does not have binary equivalence, the answer is 0. However, keeping output specifications in mind, the answer should be printed as 000 since the highest element in second line of input viz. 7 has 3 bits when represented in binary format.

Solution of Binary Equivalent TCS CodeVita:-

#include <bits/stdc++.h>

using namespace std;

#define ull       unsigned long long int

#define ll        long long int

#define loop(i,s,e)     for(ll i=(s);i<(e);i++)

#define rloop(i,s,e)    for(ll i=(s);i>=(e);i--)

#define scan(any)       for(auto &i:any) cin>>i;

#define print(any)      for(auto i:any) cout<<i<<" "; nl;

#define nl              cout<<'\n'

 #define pi 3.141592654

#define hell 1000000007

#define io ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)

#define fix(n) cout << fixed << setprecision(n)

#define input1(n) int n;cin>>n

#define input2(a, b) int a,b;cin>>a>>b

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)<(b)?(a):(b))

#define rep(i,a,b) for (__typeof((b)) i=(a);i<(b);i++)

#define ren(i,a,b) for(__typeof((a)) i=(a);i>=(b);i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define vi vector<int>

#define pii pair<int,int>

#define piii pair<pair<int,int>,int>

#define all(v) (v).begin(), (v).end()

#define sz(x) (int)x.size()

#define set(a,n) memset(a,n,sizeof(a))

void calculate(int p,vi &v1,int size,int s,int &tot)

{

if(p==size)

{

if(s==0)

tot++;

return;

}

calculate(p+1,v1,size,s+v1[p],tot);

calculate(p+1,v1,size,s,tot);

}

int main()

{

int m=0;

int n;

cin>>n;

vi v(n);

scan(v);

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

{

if(v[i]>m)

m=v[i];

}

int count=0;

while(m)

{

count++;

m=m>>1;

}

vi v1(n,0);

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

{

while(v[q])

{

if(v[q]&1)

v1[q]++;

v[q]=v[q]>>1;

}

}

int j=0;

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

{

v1[j]=count-2*v1[i];

if(v1[j]==0)

continue;

else

j++;

}

int tot=0;

calculate(0,v1,j,0,tot);

tot-=1;

tot=tot*(1+n-j)+(1<<(n-j))-1;

    vi bin(count,0);

    int i=0;

    while (tot > 0) {

        bin[i] = tot &1;

        tot = tot>>1;

    i++;

    }

    for (int p = count - 1; p >= 0; p--)

        cout << bin[p];

return 0;

}