# Solution For Single Number

Problem Statement:

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

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

Example 2:

Input: nums = [4,1,2,1,2] Output: 4

Approach:

The given problem can be solved by using the XOR operator.

XOR operator, also known as the exclusive or operator, is a bit-wise operator that takes two binary numbers and performs the logical XOR operation on each pair of corresponding bits. The result of this operation is a binary number where each bit represents whether the corresponding bits of the two operands differ.

XOR can be used to determine which bits are different between two binary numbers. When you XOR two binary numbers, the resulting bits are 1 when the corresponding bits of the two operands differ; otherwise, the resulting bits are 0.

If nums=[2,2,1], as 2^2=0 and 0^1=1, the expression evaluates to 1, which is the required output.

If nums=[4,1,2,1,2], as 4⊕1⊕2⊕1⊕2=(4⊕2)⊕1⊕1⊕2=0⊕2⊕2=0⊕0=0, the expression evaluates to 4 which is the required output.

Algorithm:

1. Initialize a variable called ‘output’ with 0.
2. Loop through each element in the array.
3. For each element, use the XOR operator to XOR it with the current value of ‘output’.
4. Update the value of ‘output’ with the result of the XOR operation.
5. After looping through all the elements, the final value of ‘output’ will be the single number that appears only once in the array.

Pseudo Code:

function singleNumber(nums):
output = 0
for num in nums:
output = output ^ num
return output

Complexity Analysis:

Time complexity: O(n). We are looping through each element in the array once.

Space complexity: O(1). We are using only constant extra space.

Code:

class Solution:
def singleNumber(self, nums: List[int]) -> int:
output = 0
for num in nums:
output = output ^ num
return output

This solution has been accepted by LeetCode and passes all test cases.

## Step by Step Implementation For Single Number

```class Solution {
public int singleNumber(int[] nums) {
// create a hashmap to store the number of times each element appears in the array
HashMap map = new HashMap();

// iterate through the array and store the number of times each element appears in the hashmap
for (int i = 0; i < nums.length; i++) {
if (!map.containsKey(nums[i])) {
map.put(nums[i], 1);
} else {
map.put(nums[i], map.get(nums[i]) + 1);
}
}

// iterate through the hashmap and return the element that appears only once
for (int key : map.keySet()) {
if (map.get(key) == 1) {
return key;
}
}

// if no element appears only once, return -1
return -1;
}
}```
```class Solution:
def singleNumber(self, nums: List[int]) -> int:
# create a hashmap to store the number of occurrences of each number
num_occurrences = {}

# iterate through the list of numbers
for num in nums:
# if the number is not in the hashmap, add it and set its value to 1
if num not in num_occurrences:
num_occurrences[num] = 1
# if the number is already in the hashmap, increment its value by 1
else:
num_occurrences[num] += 1

# iterate through the hashmap
for num, occurrences in num_occurrences.items():
# if the number of occurrences is 1, return that number
if occurrences == 1:
return num```
```var singleNumber = function(nums) {
// create hashmap to store values
const hashmap = {};

// iterate through array and store values in hashmap
for (let i = 0; i < nums.length; i++) {
if (hashmap[nums[i]]) {
// if value is already in hashmap, delete it
delete hashmap[nums[i]];
} else {
// if value is not in hashmap, store it
hashmap[nums[i]] = true;
}
}

// return the only remaining value in hashmap
return Object.keys(hashmap)[0];
};```
```class Solution {
public:
int singleNumber(vector& nums) {
int result = 0;
for(int i = 0; i < nums.size(); i++) {
result ^= nums[i];
}
return result;
}
};```
```public class Solution {
public int SingleNumber(int[] nums) {
// create a hashset to store all the unique numbers
HashSet set = new HashSet();

// loop through the array
for(int i = 0; i < nums.Length; i++)
{
// if the number is not in the hashset, add it
if(!set.Contains(nums[i]))
{
}
// if the number is already in the hashset, remove it
else
{
set.Remove(nums[i]);
}
}

// return the only remaining number in the hashset, which is the single number
return set.First();
}
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]