# Problem Link

Loop Through**Author:**pskalbhav1

# Difficulty

MEDIUM# Prerequisites

Greedy# Problem Statement

Susie attends a retroparty and wants to make new friends. But she has a strange way of making friends. Whenever she meets a stranger, she asks him/her to give her a string of length n containing only digits zero and one. She then compares it with her own string using the definition of Hamming distance:“We will define the Hamming distance between two strings s and t of the same length consisting of digits zero and one as the number of positions i, such that s_{i} isn’t equal to t_{i}.”

As besides everything else Susie loves symmetry, she wants to find for two strings s and t of length n such string p of length n, that the distance from p to s was equal to the distance from p to t.

Only if this condition is satisfied, does she make friends.

It’s time for Susie to go to bed, help her find such string p or state that it is impossible.

# Approach

One can see, that if s_{i}= t

_{i}for some i, then the value of p

_{i}isn't important for us. Really, if we make p

_{i}equal to s

_{i}then it also be equal to t

_{i}. And if we make p

_{i}not equal to s

_{i}then it also be not equal to t

_{i}. So, we have an answer that is closer or further to both of s and t.

So we interested about such position i that s_{i} ≠ t_{i}. If we make p_{i} equal to s_{i} we make p further from t. If we make p_{i} equal to t_{i} we make p further from s. It means that we need to divide these positions into two equal parts to have equidistant string. For example, we can make first of these positions closer to s, second closer to t and so on. If the number of these positions is even, we find an answer, if it is odd, answer doesn’t exist.

Time complexity — *O*(*n*).

# Solution

```
#include <bits/stdc++.h>
using namespace std;
int main()
{
int i ,cnt=0;
string a,b,c;
cin>>a;
cin>>b;
for(i=0;i<a.size();i++)
{
if(a[i]!=b[i])
cnt++;
if(cnt%2==0)
a[i]=b[i];
}
if(cnt%2!=0)
cout<<"Can't make friends";
else
cout<<a;
}
```