30 Day LeetCoding Challenge (Day 1)

The showdown has begun.

Hope you’re having a great day, in case you’re new to this post, and looking for some good editorials on the ongoing LeetCode challenge, here are the editorials for day 2 and day 4.

Back to the post, as most of you guys know, we as an individual, as an earthling, are in serious trouble from COVID-19, so I figured, why not just divert the attention for a bit, and try the super-cool coding challenge brought to you by Leetcode.

Take a look at this cool prize that they’ve got, up for grabs.

Disclaimer: I will be posting solutions to the problems post the 24 hour coding period is complete, to prevent plagiarism.

So let's begin.

Problem Statement

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,1]
Output: 1

Example 2:

Input: [4,1,2,1,2]
Output: 4

Solution

Before jumping to the solution, let's just put our thinking caps on. The statement has a couple of keywords, which are like lethal weapons for seasoned competitive programmers.

They are :

• non-empty (indicates we do not need any null checks of any sort)
• twice (more on this below)

Now, this problem can be solved in multiple ways, but I figured, the most optimal solution should be presented to all.

Intuition:

Now most of us have learned about bitwise operators, in basic math classes, or during Electronics Lab work, but hey, whatever we learn never goes to waste.

Now, the problem subtly gives us a hint that the elements in the list will be repeated twice and no more/less ( except one element, of course, :P ).

Now back to our good old math class, most of you must have heard of the XOR operator, right?

What does it do?

XOR: I have the power(ability, not the mathematical power :P) of eliminating (even) duplicates in a list of numbers.

XOR: I am Associative and Commutative.

We know, that

0 XOR 0 = 0
1 XOR 0 = 1
0 XOR 1 = 1
1 XOR 1 = 0
XOR is represented by the upwards caret 1 ^ 1 = 1 
Likewise, we can conclude
n XOR n = 0 where n is any Integer

Now, with this lethal information, we know that if we XOR the entire list of elements given to us by Leetcode, we can get the sole element required.

Armed with this information, let us code our way to victory.

class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for(int i:nums)
            ans^=i;
        return ans;
    }
}

Lesson learned: This is a constant space and linear time solution.

That's it, take a look at how it feels to get the coveted “accepted” response.

Voila, victory

Note: I will be publishing posts to the upcoming challenges once the submission window closes.

Happy Coding :D