Single Number Leetcode Solution

Difficulty Level Easy
Frequently asked in Adobe Airbnb Amazon Apple Atlassian Bloomberg Facebook Google Microsoft Palantir Technologies SAP TCS Twitter Uber Yahoo ZohoViews 14579

Problem Statement

Single Number Leetcode Solution – We are given a non-empty array of integers and need to find an element that appears exactly once. It is given in the question that every element appears twice except for one.

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

Explanation for Single Number Leetcode Solution:

In the first eg. 1 appears exactly once however, 2 appears twice so the answer is 1

In the second eg. 1’s and 2’s appear twice and hence answer is 4.

In the final eg. 1 appears only once, hence the answer is 1

Approach

Idea:

This question is very easy if there were no constraints about the time and space complexity.

For the time being, let’s assume there are no constraints.

In this case, there are multiple ways to solve this question.

  • We can keep a hashmap and count the number of times an element appears. We can run a loop on hashmap and print the element having the count as 1.
  • We can sort the elements and check if a[i] ≠ a[i-1] & a[i]≠ a[i+1] (assuming we take care of the first and last element), for i in size of array n and print a[i]

Since we are bound to use constant memory and size, we discard the first and second solutions.

The only way to solve this problem following the given constraint is to use the concept of XOR.

 

Concept

  • XOR of zero and some bit returns that bit
    • a^0 = a
  • XOR of two same bits returns 0
    • a^a = 0
  • XOR of a^b^a for some bits a and b returns b
    • a^b^a = (a^a)^b = 0^b = b

So we can XOR all bits together to find the unique number.

Code

C++ Program of Single Number:

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for(int x: nums) {
            res ^= x;
        }
        return res;
    }
};

Java Program of Single Number:

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

 

Python Program of Single Number:

class Solution(object):
    def singleNumber(self, nums):
        res = 0
        for x in nums:
            res ^= x
        return res

 

Complexity Analysis for Single Number Leetcode Solution

  • Time complexity: O(n).
    • We only iterated through the array nums, so the time complexity is the number of elements in the given array
  • Space complexity: O(1)
    • no extra space is used other than a variable res to store the answer

Reference: https://en.wikipedia.org/wiki/Exclusive_or

Translate »