3ms C++ using XOR - simple solution


  • 1
    A
    class Solution {
    public:
        char findTheDifference(string s, string t) {
            int i = 0, res = 0;
            
            for (i = 0; i < s.size(); i++) {
                res ^= s[i] ^ t[i];
            }
            
            return (res ^ t[i]); // t[i] is the last element in t
        }
    };
    

  • 0
    F

    thanks for posting, but would you mind specifying how and why you were doing this way?


  • 0
    A

    @facss When I attempted this problem it reminded me of a similar one I've done here on LeetCode. It was 136. Single Number where all elements appeared twice except one. The solution was to use XOR, because all of the integers would cancel out except one.

    So I used the same approach for this problem, because letters are simply ASCII values from 0-255. So the letter a would be the value 97 on the ASCII table. To explain why the letters cancel each other out think of a simple problem first like an array of [3,5,3]. In binary 3 is 0011 and 5 is 0101. If you were to XOR 3 with 3 the result would be 0000, which will produce a value of 97 or the character a.

    However, since we are iterating through an array mentioned earlier, 3 would be first XOR'ed with 5. The result would be 0110. Then XOR that result with 3, which will produce 0101 and is equal to 5. So the order of the elements does not matter as long as there is two of every element except one as is the case with this problem. This also works when XOR'ing strings like "aaa" and "aa" together.


  • 0
    F

    Thanks for heading up. I have already figured it out. You are awesome with this, bro.


  • 0
    H

    thank you! i get it.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.