Find the Difference (Beautiful Arrangement) Problem Solution

Posted in

Find the Difference (Beautiful Arrangement) Problem Solution
maazbinasad

Maaz Bin Asad
Last updated on February 21, 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

    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
    

    Leave a Comment on this Post

    0 Comments