# Find the Difference (Beautiful Arrangement) Problem Solution

Posted in

Last updated on July 20, 2024

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``

### 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) {

// iterate each character and keep XORing with `answer`
for(char cs : s) answer ^= cs;
for(char ct : t) answer ^= ct;

}

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) {

// iterate each character and keep XORing with `answer`
for(char cs : s.toCharArray()) answer ^= cs;
for(char ct : t.toCharArray()) answer ^= ct;

}

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):

# iterate each character and keep XORing with `answer`
for cs in s: answer ^= ord(cs)
for ct in t: answer ^= ord(ct)

``````e