# DIFSTR - Editorial

Author: Deepak Barnwal
Tester: Shubham Anand Jain
Editorialist: Nishank Suresh

Easy

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);
#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()
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
5 Likes

I think, there is something wrong with this questionâ€™s test cases, I mean look at below code (accepted during contest), The task is to find different string from given strings.

#include <bits/stdc++.h>

using namespace std;
#define ll long long

int main()
{
ll test, n;
std::cin >> test;

while (test--)
{
std::cin >> n;
std::string text[n], res;

for (ll i = 0; i < n; i++)
{
std::cin >> text[i];
res.push_back('0');
}

ll j = 0;
for (ll i = 0; i < n; i++)
{
if (text[i] == res)
{
if (res[j] == '0')
res[j] = '1';
else
res[j] = '0';

j++;
}
}
std::cout << res << "\n";
}

return 0;
}

But entering below Inputs, Output string is similar to given strings:
Input:

1
4
1101
1000
1001
0000

Output:

1000

Input:

1
3
101
100
000

Output:

100

So, @iceknight1093 How it got AC ?, Please correct me, If Iâ€™m wrong!

1 Like

I wonder if there are any tests.

8 Likes

Not all those who wonder are lost

A different approach: Solution: 50060264 | CodeChef

This is actually based on something called the Hilbert Hotel
Nice Video on the topic: How An Infinite Hotel Ran Out Of Room - YouTube

6 Likes

It was the easiest approach bro! well done

Thnx!

Nailed itâ€¦i never thought of thisâ€¦took me a while to get it lol

1 Like

I have implemented my solution remembering this video. I am following this channel for long time.

I did this problem easily by considering:

• there are N strings given
• if I see the number of consecutive 1s from the most significant bit, there are N + 1 cases available.

eg: for N = 5, there are 6 possibilities.

• there can be 0 consecutive 1s from left(eg, 01111)
• there can be 1 consecutive 1s from left(eg, 10000)
â€¦
• there can be 5 consecutive 1s from left(eg, 11111)

I see which among these N + 1 cases is not in the N cases given and print it : )

• if i find that 3 is not present, i print â€ś11100â€ť.
• if i find that 4 is not present, i print â€ś11110â€ť.
• if i find that 1 is not present, i print â€ś10000â€ť.
and so onâ€¦

Submission Link: Solution: 50070991 | CodeChef

1 Like

Take a string of length n which has all oneâ€™s. If this isnâ€™t already in the given strings you have the answer else you can try to put zero at each position, you can put zero at N indices so one of them surely will not be present in the given string as we have tried N+1 strings.

1 Like

Elegant solution indeed : )

1 Like

I tried the randomized approach but got TLE. Can anyone please guess why ?

How is it any different from the setterâ€™s solution?

I am sorry, I had not seen the setterâ€™s solution. Smh!

No problem, that was a nice approach nonetheless.

Even on the sample, running your code a few times shows that every once in a while, it generates an extremely large number of strings because it generates the same one over and over again (around 5e5 times locally).

Easy fix: use a better generator (fixed code)

1 Like

def bot(a):
cnt=0
while a!=0:
a=a>>1
cnt+=1
return cnt
print(bot(7))

import math as m
for T in range(int(input())):
n=int(input())
if n==1:
st=int(input())
if st==1:
print(0)
print(1)
else:
s=set()
st=input()
temp2=int(â€ś0bâ€ť+st,2)
temp=temp2+1
flag=0
for i in range(n-1):
st=input()
c=int(â€ś0bâ€ť+st,2)
for i in range(n):
if temp in s:
temp+=1
else:
v=bot(temp)
if v>n:
flag=1
break
else:
ans=""+bin(temp)
print(ans[2:])
break
#print("#")
if flag==1:
#print("\$")
for i in range(n):
if temp2 in s:
temp2-=1

else:
#v=m.ciel(m.log2(temp))
ans=""+bin(temp2)
print(ans[2:])
break
#print(bin(temp2[2:]))

can anyone tell where my solution fails

There are several cases where your code fails.
Here are a couple:

Input
2
1
1
2
10
11