Alkesh

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.

Example 2:

Input: nums = [-1, 0]
Output: [-1, 0]

Example 3:

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

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.

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;

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;

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]

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

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;
    }
};

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
}

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];
};

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]
Share this post!