# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

* Author:* Deepak Barnwal

*Shubham Anand Jain*

**Tester:***Nishank Suresh*

**Editorialist:**# DIFFICULTY:

Easy

# PREREQUISITES:

None

# PROBLEM:

Given N binary strings of length N each, find a binary string of length N which is different from all of them.

# QUICK EXPLANATION:

If the input strings are S_1, S_2, \dots, S_N, one possible solution is to set ans[i] to be the opposite of S_i[i].

# EXPLANATION:

The quick explanation says it all!

There are 2^N binary strings of length N, and N < 2^N for every N \geq 1 so an answer always exists.

Since the length of the strings equals their number, we can use the i-th position of the answer to make it different from the i-th string. That leads to the following construction:

Create a binary string of length N whose i-th character is the opposite of the i-th character of the i-th input string.

This ensures that the created strings differs from each input string at at least one position, which is exactly what we want.

# ALTERNATE SOLUTIONS:

The above solution is not the only one - several others exist as well. A couple are outlined below.

### Solution 1

Since N strings are given, one can try N+1 different strings and check whether each of them is among the given strings.

The pigeonhole principle tells us that at least one of these N+1 strings will be an answer.

To make implementation easy, these N+1 strings can be the N-bit binary representations of 0, 1, 2, \dots, N.

N is small enough that this \mathcal{O}(N^3) solution works comfortably.

### Solution 2

N is much less than 2^N, so the space of possible answers is extremely large. So large, in fact, that one can generate a random binary string and check whether it is in the given set - and if it is, repeat till one which isnâ€™t is generated.

The probability that a random binary string is not among the given N is 1 - \frac{N}{2^N}. The expected number of trials till an answer is found is thus \frac{2^N}{2^N - N}, which is \leq 2 for all N \geq 1. For N\geq 10 itâ€™s basically 1.

Each trial works in \mathcal{O}(N^2) (comparing the generated string against all existing strings) so this runs in expected \mathcal{O}(N^2)

If you have a different solution, feel free to share it in the comments below!

# TIME COMPLEXITY:

\mathcal{O}(N) or \mathcal{O}(N^2) or \mathcal{O}(N^3) per testcase, depending on implementation.

# SOLUTIONS:

## Setter's Solution

```
#include "bits/stdc++.h"
using namespace std;
#define FastIO ios_base::sync_with_stdio(false); cin.tie(NULL);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define int long long
void solve(int TC){
int n,i;
cin>>n;
string s[n];
for(i=0; i<n; i++){
cin>>s[i];
}
int a;
for(i=0; i<n; i++){
a = (s[i][i] - '0');
cout<<!a;
}
cout<<'\n';
}
signed main(){
FastIO;
int Test = 1;
cin>>Test;
for(int i=1; i<=Test; i++){
solve(i);
}
return 0;
}
```

## Tester's Solution

```
//By TheOneYouWant
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
int main(){
fastio;
int tests;
cin >> tests;
while(tests--){
int n;
cin >> n;
string s[n];
string ans;
for(int i = 0; i < n; i++){
cin >> s[i];
if(s[i][i]=='0') ans += '1';
else if(s[i][i]=='1') ans += '0';
}
cout << ans << endl;
}
return 0;
}
```

## Editorialist's Solution

```
for _ in range(int(input())):
n = int(input())
have = set()
for i in range(n):
s = input()
have.add(s)
for i in range(n+1):
cur = ''
for bit in range(n):
cur += '1' if i&(1<<bit) else '0'
if cur in have:
continue
print(cur)
break
```