# [leetcode] Single Number - 30Day LeetCoding Challenge Day 1

## 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)
``````