Find the Difference (Beautiful Arrangement) Problem Solution

Problem

Given two strings, ‘s’ and  ‘t’ have all the characters the same except one, which was inserted at some random position. Find this additional character.

Sample Input

s = "abcd"
t = "abcde"

Sample Output

e

Explanation

e is added to ‘t’

Approach

We will use bitwise XOR to solve this problem. Since for an arbitrary element ‘x’ :

x ^ x = 0 – (i)

All the elements in both the strings would appear an even several times except one, which is the answer. Therefore, according to (i), we can perform XOR of all the elements in the string and return the remaining character, which will be our answer.

Complexity Analysis

The time complexity is O(N), with no extra space required

C++ Program

#include <iostream>
using namespace std;

// function to find the letter added to second string
char findTheDifference(string s, string t) {
    
        char answer = 0;
        // iterate each character and keep XORing with `answer`
        for(char cs : s) answer ^= cs;
        for(char ct : t) answer ^= ct;
        
        // return the answer
        return answer;
    }
    
int main() {
    string s = "abcd";
    string t = "abcde";
    cout << findTheDifference(s, t);
}

Output

e

Java Program

import java.io.*;

class Solution {
    
    // function to find the letter added to second string
    public static char findTheDifference(String s, String t) {
    
        char answer = 0;
        // iterate each character and keep XORing with `answer`
        for(char cs : s.toCharArray()) answer ^= cs;
        for(char ct : t.toCharArray()) answer ^= ct;
        
        // return the answer
        return answer;
    }
    
    public static void main (String[] args) {
        String s = "abcd";
        String t = "abcde";
        System.out.print(findTheDifference(s, t));
    }
}

Output

e

Python Programming

# function to find the letter added to second string
def findTheDifference(s, t):
    answer = 0
    
    # iterate each character and keep XORing with `answer`
    for cs in s: answer ^= ord(cs)
    for ct in t: answer ^= ord(ct)
    
    # return the answer
    return chr(answer)

s = "abcd"
t = "abcde"
print(findTheDifference(s, t))

Output

e