LT09-Editorial

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 si isn’t equal to ti.”

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 si = ti for some i, then the value of pi isn't important for us. Really, if we make pi equal to si then it also be equal to ti. And if we make pi not equal to si then it also be not equal to ti. So, we have an answer that is closer or further to both of s and t.

So we interested about such position i that si ≠ ti. If we make pi equal to si we make p further from t. If we make pi equal to ti 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;
}