Introduction
Today, I joined the "30-Day LeetCoding Challenge" that leetcode provides with algorithm questions every day in April 2020. Almost all people must stay indoors and work from home including computer engineers because of COVID-19. Thinking it positive, this is a nice opportunity to improve my skills and prepare for a future job interview.
In addition, I will get 600coins + extra leetcoins through this program if I solved all of the questions. I need to make 5000 coins to have a T-shirt of leetcode. So, I am joining this event.
Question
The array list that appears twice apart from one number is given as an argument. You need to find a non-duplicated number and return it.
Besides, time complexity should be O(1). Also, space complexity should be O(1) if you can.
Solution
Bitwise XOR approach is appropriate for this question to solve this without using any extra space. XOR has a feature that the number can be back if it flipped twice. For instance, this equation 2 ^ 2 returns 0. If every node is operated by XOR, the leftover number will be an answer.
Submission.
Here is the result of the submission in leetcode.
Time complexity: O(n)
Space complexity: O(1)
Runtime: 80 ms, faster than 95.52% of Python3 online submissions for Single Number.
Memory Usage: 16.1 MB, less than 6.56% of Python3 online submissions for Single Number.
Next challenges:
I am not sure why the performance of the memory usage is not good...
Here is python code.
def singleNumber(self, nums: List[int]) -> int:
res: int = 0
for n in nums:
res ^= n
return res
https://github.com/nk18chi/leetcode/blob/master/solutions/single_number/index.py
Bonus
I found another interesting solution by using a set-list. At first, the array list converts into a set-list and calculates the sum of the set-list. Then, that sum multiple by two and subtract the sum of the original array-list. the answer must be left.
Here is code
def singleNumber(self, nums: List[int]) -> int:
return sum(set(nums)) * 2 - sum(nums)
