[LeetCode] 389. Find the Difference

Problem

Image linked to LeetCode problem page

Explanation

The XOR (^) operation has two fundamental properties:

• Self-inverse: ##x^x=0##
• Identity with zero: ##x^0=x##

It also has two additional properties that ensure the order of XOR operations does not matter.

• Commutative: ##a^b=b^a##
• Associative: ##(a^b)^c=a^(b^c)##

Because of these properties, identical values XOR-ed together cancel each other out regardless of their order.

Solution

class Solution {
    public char findTheDifference(String s, String t) {
        char result=0;
        for(char c:s.toCharArray()){
            result^=c;
            
        }
        for(char c:t.toCharArray()){
            result^=c;
        }
        return result;
        
    }
}

Example

In this problem, we are given two strings:

• ##s="abc"## the original string
• ##t="adbc"## the same string with one extra character added ##d##

Conceptually, XOR-ing all characters from both strings together yields the difference:

a ^ b ^ c ^ a ^ d ^ b ^ c
= (a ^ a) ^ (b ^ b) ^ (c ^ c) ^ d
= 0 ^ 0 ^ 0 ^ d
= d

Every character that appears in both strings cancels itself out. The only character that does not have a matching pair ##d## remains.

 

The code iterates through each string and repeatedly apply the XOR operation to a running variable ##result##. Due to XOR's associative and commutative properties, this step-by-step process produces the same final results as the mathematical expression above. Below is a walkthrough showing how ##result## is updated one character at a time. 

 

Iterating through ##s="abc"##:

Character	Binary Value	result after XOR
'a'	01100001	01100001
'b'	01100010	00000011
'c'	01100011	01100000

 

Iterating through ##t="adbc"##:

Character	Binary Value	result after XOR
'a'	01100001	00000001
'd'	01100100	01100101
'b'	01100010	00000111
'c'	01100011	01100100