Background: We all are home for the current pandemic situation. Leetcode has taken this opportunity to throw a challenge for the users (which is positive, I think).
The challenge is titled 30-Day LeetCoding Challenge. I have started it since yesterday and wish to complete it and write blog post for each problem I solve in a day. This is just to keep myself motivated to stay at home and give something back to the community. As a disclaimer, I have taken problem statements and examples from leetcode. Without any more introduction, I will jump into the problem, how I solved it and link to my code. If you find this helpful, give me a poke!

Problem Title: Single Number

Description: Given a non-empty array of integers, every element appears twice except for one. Find that single one. Your algorithm should have a linear run time complexity i.e. O(n). Could you implement it without using extra memory?

Example 1:

Input: [2,2,1]
Output: 1 (because 1 the only number that is appearing once)

Example 2:

Input: [4,1,2,1,2]
Output: 4 (because 1 the only number that is appearing once)

Solution: I solved this problem using bitwise XOR. The idea is, when you XOR a number with itself, you will get 0. For example, 2441139 ⊗ XOR 2441139 = 0.
Now, say, we have 5 numbers like 3, 4, 9, 3, 9. If we XOR these numbers from begin to end, we will end up XORing 3 twice and 9 twice. Both of them will make the result 0 and 4 will remain intact since any number XOR with 0 ends up to that number. (If you don’t get the idea still, I would suggest you to do the calculations on paper, you should get it for sure!)

Code: Here is my C++ code for it.

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int sum = 0;
        for(auto x: nums)
            sum ^= x;
        return sum;

    }
};

If you want to learn more about bitwise operation, this link is a good resource in my opinion.

If you find this helpful or want me to improve my explanation(I think that’s more probable) or want to shout out of anger because of my crappy writing, you can post your comments :).

Stay safe at home! Happy Coding! :)

Follow me on twitter.