DEV Community

loading...
Cover image for 30-Day LeetCoding Challenge (Day-1)

30-Day LeetCoding Challenge (Day-1)

late_riser profile image Sadi Updated on ・2 min read

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.

Discussion (4)

pic
Editor guide
Collapse
ac000 profile image
Andrew Clayton

While I like the XOR trick. Seeing as this is #c, here's some C code...

#include <stdio.h>

static const int array[] = { 3, 4, 9, 3, 9 };

int main(void)
{
        int i = 0;
        int sum = 0;
        int n = sizeof(array) / sizeof(array[0]);

        for ( ; i < n; )
                sum ^= array[i++];

        printf("%d\n", sum);

        return 0;
}
Collapse
late_riser profile image
Sadi Author

Nice code. My one is C++ though!

Collapse
ac000 profile image
Andrew Clayton

OK. I was maybe too subtle.

I was really just pointing out the fact that you posted C++ code to the #c topic, when you actually wanted the #cpp one...

Remember, C != C++, I see people conflating the two all too often...

Thread Thread
late_riser profile image
Sadi Author • Edited

Oh I see! My bad! Actually what happened is, I gave tag as 'c++' which I guess the editor cannot differentiate. It just omits the '++'. Now I have given cpp which works. Thanks for the correction though :)