Solution Review: Single Number

We try to solve the problem using a more optimal way.

Solution review: Bit manipulation

We are dealing with bit manipulation and want to solve these problems with Bitwise operators.

Concepts

If we take the XOR of zero and a bit, it will return that bit.

a ^ 0 = a

If we take the XOR of two same bits, it will return 0.

a ^ a = 0

For n numbers, the below math can be applied.

a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b;

For example:

1 ^ 5 ^ 1 = (1 ^ 1) ^ 5 = 0 ^ 5 = 5;

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

Algorithm

• Initialize a variable to 0.
• Iterate over all the elements and store the value in the variable.

Solution

Here is the logic behind this algorithm.

Java

class SingleNumber {
    private static int singleNumber(int[] nums) {
        int xor = 0;
        for (int num : nums) {
            xor ^= num;
        }
        return xor;
    }

    public static void main(String[] args) {
        int[] nums = {4, 1, 2, 9, 1, 4, 2};
        System.out.println("Element appearing one time is " + singleNumber(nums));
    }
}

Python

def singleNumber(nums):
    xor = 0
    for num in nums:
        xor ^= num
    return xor

nums = [4, 1, 2, 9, 1, 4, 2]
print("Element appearing one time is", singleNumber(nums))

JavaScript

const SingleNumber = array => {

    function helper (nums) {
        let xor = 0;
        for(let num of nums) {
            xor ^= num;
        }
        return xor;
    }

    return helper (array);
}

const array = [4, 1, 2, 9, 1, 4, 2];
console.log (`Element appearing one time is ${SingleNumber (array)}`);

C++

#include <iostream>

using namespace std;

void SingleElement(int *arr, int n) {
    int xr = 0;
    for (int i = 0; i < n; i++) {
        xr ^= arr[i];
    }
    cout << "Element appearing one time is:  " << xr << endl;
}

int main() {
    int arr[] = {4, 1, 2, 9, 1, 4, 2};
    SingleElement(arr, sizeof(arr) / sizeof(arr[0]));
    return 0;
}

TypeScript

export const SingleNumber = (array: number[]): number => {
    function helper(nums: number[]): number {
        let xor: number = 0;
        for (let num of nums) {
            xor ^= num;
        }
        return xor;
    }

    return helper(array);
}

const array: number[] = [4, 1, 2, 9, 1, 4, 2];
console.log(`Element appearing one time is ${SingleNumber(array)}`);

Complexity analysis

Time complexity: O(n)

n is the number of elements in the array since we must iterate over all the elements to find a single number. So, the best and the worst-case time is O(n).

Space complexity: O(1)

The space complexity is O(1). No extra space is allocated.