# Solution Review: Single Number

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

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.

Coding Interview QuestionsData Structures and AlgorithmsArraysBit Manipulation

Gopi is an engineering leader with 12+ of experience in full-stack development—a specialist in Java technology stack. He worked for multiple startups, the European govt, and FAANG in India and Europe.

Members Public

## Leetcode 217: Contains Duplicate

This question marks the first problem when working on duplicate data, either integers or strings etc. Companies that have asked this in their coding interview are Amazon, Apple, Netflix, Google, Microsoft, Adobe, Facebook, and many more top tech companies. Problem statement Given an integer array nums, return true if any

Members Public

## Leetcode 121: Best Time To Buy and Sell Stock

The Best time to buy and sell stock problem is a classic problem that can be solved using the Greedy approach. This is one of the most popular questions asked in such interviews. Companies that have asked this in their coding interview are Facebook, Amazon, Apple, Netflix, Google, Microsoft, Adobe,

Members Public

## Arrays From Zero To Mastery: A Complete Notes For Programmers

This article discusses array data structure with sketches, memory diagrams, array capacity vs. length, strengths & weaknesses, big-O complexities, and more!