Crash Code Part-2 (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 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.

Similaly, 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

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.

Solve

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156

#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);
	

	
}

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