DEV Community

Alkesh Ghorpade
Alkesh Ghorpade

Posted on • Originally published at alkeshghorpade.me

LeetCode - Single Number III

Problem statement

Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.

You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.

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

Example 1:

Input: nums = [1, 2, 1, 3, 2, 5]
Output: [3, 5]
Explanation:  [5, 3] is also a valid answer.
Enter fullscreen mode Exit fullscreen mode

Example 2:

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

Example 3:

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

Constraints:

- 2 <= nums.length <= 3 * 10^4
- 2^31 <= nums[i] <= 2^31 - 1
- Each integer in nums will appear twice, only two integers will appear once.
Enter fullscreen mode Exit fullscreen mode

Explanation

Sorting

We sort the array elements and compare the adjacent elements.
We can easily get the non-repeating element using the above approach.

A C++ snippet of the above approach is as below:

sort(nums, nums + n);
vector<int> result;

for (int i = 0; i < n - 1; i = i + 2) {
    if (nums[i] != nums[i + 1]) {
        result.push_back(nums[i]);
        i = i - 1;
    }
}

if (result.size() == 1)
    result.push_back(nums[n - 1]);

return result;
Enter fullscreen mode Exit fullscreen mode

The time complexity of the program is O(nlog(n)), and the space complexity
is O(1).

HashMap

The problem can be solved in O(n) using a HashMap.
We run a loop over the array and count the number of occurrences
of each element in the array.

We iterate over the hash and print the two numbers that appeared only
once.

A C++ snippet of the above approach is as below:

int n = nums.size();
vector<int> result;

if(n == 0) {
    return result;
}

map<int, int> m;

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

vector<int> result;

for(auto i = m.begin(); i != m.end(); i++) {
    if(i->second == 1) {
        result.push_back(i->first);
    }
}

return result;
Enter fullscreen mode Exit fullscreen mode

The time complexity of the program is O(n), and the space complexity
is O(n).

XOR operator

The program can be solve in O(n) time complexity and O(1)
space complexity using XOR operation.

Let a and b be the elements that appears exactly once in nums array.
We first compute the XOR of all the array elements.

xor = nums[0]^nums[1]^nums[2]....nums[n - 1]
Enter fullscreen mode Exit fullscreen mode

All the bits that are set in the above xor variable will be
set in one non-repeating element either a or b.

We take the any set bit of xor and divide the elements of the array
in two sets. One set of elements with same bit set and another with the
same bit not set.

We do XOR of all the elements in the first set which will return the first
non-repeating element, and doing the same in another set will return the
second non-repeating element.

Let's check the algorithm first.

- set xorResult = nums[0]
  a = 0, b = 0, i = 0
  vector<int> result

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

- set setBitNo = xorResult == INT_MIN ? 0 : xorResult & ~(xorResult - 1)

- loop for i = 0; i < nums.size(); i+=
  - if nums[i] & setBitNo
    - a ^= nums[i]
  - else
    - b ^= nums[i]

- result.push_back(a)
- result.push_back(b)

- return result
Enter fullscreen mode Exit fullscreen mode

The time complexity of the above approach is O(n), and the space complexity is O(1).

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

C++ solution

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int xorResult = nums[0];
        int a = 0, b = 0, i;
        vector<int> result;

        for(i = 1; i < nums.size(); i++) {
            xorResult ^= nums[i];
        }

        int setBitNo = xorResult == INT_MIN ? 0 : xorResult & ~(xorResult - 1);

        for(i = 0; i < nums.size(); i++) {
            if(nums[i] & setBitNo) {
                a ^= nums[i];
            } else {
                b ^= nums[i];
            }
        }

        result.push_back(a);
        result.push_back(b);
        return result;
    }
};
Enter fullscreen mode Exit fullscreen mode

Golang solution

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

    for _, num := range nums {
        xorResult = xorResult ^ num
    }

    setBitNo := xorResult & (-xorResult)

    result := make([]int, 2)

    for _, num := range nums {
        if num & setBitNo == 0 {
            result[0] ^= num
        } else {
            result[1] ^= num
        }
    }

    return result
}
Enter fullscreen mode Exit fullscreen mode

Javascript solution

var singleNumber = function(nums) {
    let xorResult = 0;
    let a = 0, b = 0, i = 0;

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

    let setBitNo = xorResult & ~(xorResult - 1);

    for(i = 0; i < nums.length; i++) {
        if((nums[i] & setBitNo) === 0)
            a ^= nums[i];
        else
            b ^= nums[i];
    }

    return [a, b];
};
Enter fullscreen mode Exit fullscreen mode

Let's dry-run our algorithm for Example 1.

Input: nums = [1, 2, 1, 3, 2, 5]

Step 1: xorResult = nums[0]
                  = 1

Step 2: int a = 0, b = 0, i
        vector<int> result

Step 3: loop for i = 1; i < nums.size(); i++
            xorResult ^= nums[i]

        The xorResult is 6 (0110)

Step 4: setBitNo = xorResult == INT_MIN ? 0 : xorResult & ~(xorResult - 1)
                 = 6 == INT_MIN ? 0 : xorResult & ~(xorResult - 1)
                 = false ? 0 : xorResult & ~(xorResult - 1)
                 = xorResult & ~(xorResult - 1)
                 = 6 & ~(6 - 1)
                 = 6 & ~5
                 = 6 & -6
                 = 2

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

            if nums[i] & setBitNo
               nums[0] & 2
               1 & 2
               0001 & 0010
               0
               false
            else
               b ^= nums[i]
                  = b ^ nums[i]
                  = 0 ^ nums[0]
                  = 0 ^ 1
                  = 1
        i++
        i = 1

Step 6: loop i < nums.size()
            1 < 6
            true

            if nums[i] & setBitNo
               nums[1] & 2
               2 & 2
               0010 & 0010
               2
               true
               a ^= nums[i]
                  = a ^ nums[1]
                  = 0 ^ 2
                  = 2

        i++
        i = 2

Step 7: loop i < nums.size()
            2 < 6
            true

            if nums[i] & setBitNo
               nums[2] & 2
               1 & 2
               0001 & 0010
               0
               false
            else
               b ^= nums[i]
                  = b ^ nums[i]
                  = 1 ^ nums[2]
                  = 1 ^ 1
                  = 0
        i++
        i = 3

Step 8: loop i < nums.size()
            3 < 6
            true

            if nums[i] & setBitNo
               nums[3] & 2
               3 & 2
               0011 & 0010
               2
               true
                a ^= nums[i]
                  = a ^ nums[3]
                  = 2 ^ 3
                  = 1

        i++
        i = 4

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

            if nums[i] & setBitNo
               nums[4] & 2
               2 & 2
               0010 & 0010
               2
               true
               a ^= nums[i]
                  = a ^ nums[4]
                  = 1 ^ 2
                  = 3

        i++
        i = 5

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

            if nums[i] & setBitNo
               nums[5] & 2
               5 & 2
               0101 & 0010
               0
               false
            else
              b ^= nums[i]
                  = b ^ nums[i]
                  = 0 ^ nums[5]
                  = 0 ^ 5
                  = 5

        i++
        i = 6

Step 11: loop i < nums.size()
            6 < 6
            false

Step 12: result.push_back(a)
         result.push_back(3)
         result = [3]

         result.push_back(b)
         result.push_back(5)
         result = [3, 5]

         return result

We return the result as [3, 5]
Enter fullscreen mode Exit fullscreen mode

Top comments (0)