136. Single Number — LeetCode(Python)

I got you!

Problem:

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

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [1]
Output: 1

Constraints:

• 1 <= nums.length <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104
• Each element in the array appears twice except for one element which appears only once.

Solution(s):

1. Hash Map —

Solution —

The code is redundant, so let’s skip that part.

Explanation —

We create a Python dictionary after looping over every element in the array nums.

The keys in this dictionary will be the elements in the array and the values will be the number of times they are present.

We then iterate over this dictionary to find which key has a value of ‘1’. That key is returned.

Time and Space Complexity —

Creation of the dictionary takes linear time and space, and searching for the key with value ‘1’ also takes linear time.

Thus, if n is the number of elements in the array nums,

Time Complexity: O(n)

Space Complexity: O(n)

2. Bit Manipulation —

Solution —

a = 0
for n in nums:
    a ^= n
return a

Explanation —

Here, we use the XOR operation (^). The properties that we’ve used are:

a^a = 0

0^a = a

a^b = b^a

Thus, when we iterate over the array, we use the XOR operation on every single element with the variable a and store the value of the expression in the same a variable.

Since all elements except one appear exactly twice, their XOR would lead to a ‘0’ and XOR between ‘0’ and the single number would be equal to the number itself, we are left with the value of the number in our variable a.

Time and Space Complexity —

Looping over the array takes linear time and no extra storage was required in our solution.

Thus, if n is the number of elements in the array nums,

Time Complexity: O(n)

Space Complexity: O(1)

Feel free to ask any related questions in the comment section or the links provided down below.

I don’t have friends:

Let’s be friends!

Connect with me on:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏