DEV Community

Alkesh Ghorpade
Alkesh Ghorpade

Posted on • Originally published at alkeshghorpade.me

LeetCode - Single Number

Problem statement

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.

Problem statement taken from: https://leetcode.com/problems/single-number.

Example 1:

Input: nums = [2, 2, 1]
Output: 1
Enter fullscreen mode Exit fullscreen mode

Example 2:

Input: nums = [4, 1, 2, 1, 2]
Output: 4
Enter fullscreen mode Exit fullscreen mode

Example 3:

Input: nums = [1]
Output: 1
Enter fullscreen mode Exit fullscreen mode

Constraints:

- 1 <= nums.length <= 3 * 10^4
- -3 * 10^4 <= nums[i] <= 3 * 10^4
- Each element in the array appears twice except for one element which appears only once.
Enter fullscreen mode Exit fullscreen mode

Explanation

Brute force solution

The brute force solution is to check if every element appears once or not. Once an element with a single occurrence is found, we return that element. The time complexity of the above approach is O(N^2).

The time complexity can be reduced to O(N) by using hashing. We traverse all the elements in an array and put them in the hash table. Array element will be the key in the hash table, and its value will be the count of occurrences of that element in the array.

A C++ snippet for this approach is as below:

int singleNumber(vector<int>& nums) {
    map<int, int> m;

    for(int i = 0; i < nums.size(); i++) {
        m[nums[i]]++;
    }

    for(auto const & [key, value]: m) {
        if(value == 1) {
            return key;
        }
    }

    return -1;
}
Enter fullscreen mode Exit fullscreen mode

The time complexity is reduced to O(N), but space complexity has increased to O(N).

Optimized solution

We can reduce the space complexity to O(1), by using a single int variable. We can use the arithmetic XOR operator ^. An XOR operator returns 0 when the operands are similar.

3 ^ 1
=> 2

3 ^ 2
=> 0

3 ^ 0
=> 3
Enter fullscreen mode Exit fullscreen mode

Since every element in an array appears twice except one, the XOR for all duplicates will return 0. And XOR for any non-zero number with zero will return the same number. We need to iterate over the array and perform XOR for all the elements.

Let's check the algorithm now.

- initialize singleNum = 0

- loop for i = 0; i < nums.size(); i++
  - singleNum ^= nums[i]

- return singleNum
Enter fullscreen mode Exit fullscreen mode

Let's check out our solutions in C++, Golang, and Javascript.

C++ solution

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int singleNum = 0;

        for(int i = 0; i < nums.size(); i++) {
            singleNum ^= nums[i];
        }

        return singleNum;
    }
};
Enter fullscreen mode Exit fullscreen mode

Golang solution

func singleNumber(nums []int) int {
    singleNum := 0

    for i := 0; i < len(nums); i++ {
        singleNum ^= nums[i]
    }

    return singleNum
}
Enter fullscreen mode Exit fullscreen mode

Javascript solution

var singleNumber = function(nums) {
    let singleNum = 0;

    for(let i = 0; i < nums.length; i++) {
        singleNum ^= nums[i];
    }

    return singleNum;
};
Enter fullscreen mode Exit fullscreen mode

Let's dry-run our algorithm to see how the solution works.

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

Step 1: singleNum = 0

Step 2: loop for i = 0; i < nums.size()
          0 < 5
          true

          singleNum ^= nums[i]
                     = singleNum ^ nums[0]
                     = 0 ^ 4
                     = 4

          i++
          i = 1

Step 3: i < nums.size()
          1 < 5
          true

          singleNum ^= nums[i]
                     = singleNum ^ nums[1]
                     = 4 ^ 1
                     = 5

          i++
          i = 2

Step 4: i < nums.size()
          2 < 5
          true

          singleNum ^= nums[i]
                     = singleNum ^ nums[2]
                     = 5 ^ 2
                     = 7

          i++
          i = 3

Step 5: i < nums.size()
          3 < 5
          true

          singleNum ^= nums[i]
                     = singleNum ^ nums[3]
                     = 7 ^ 1
                     = 6

          i++
          i = 4

Step 6: i < nums.size()
          4 < 5
          true

          singleNum ^= nums[i]
                     = singleNum ^ nums[4]
                     = 6 ^ 2
                     = 4

          i++
          i = 5

Step 7: i < nums.size()
          5 < 5
          false

Step 8: return singleNum

So we return the answer as 4.
Enter fullscreen mode Exit fullscreen mode

Top comments (1)

Collapse
 
bellatrix profile image
Sakshi • Edited

You are really putting great efforts in making people understand the code and problem better. Will surely recommend this blog to my juniors!🙌

XOR rocks

It is super helpful!!