# Solution Review: Single Number

Single Number coding question, can be easily solved with XOR bitwise technique with linear time complexity.

## Table of Contents

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

. No extra space is allocated.*O*(1)

## Gopi Gorantala Newsletter

Join the newsletter to receive the latest updates in your inbox.