# .css-df1pn7{display:block;width:16rem;}     # Single Number

Sonu Kumar Saw
·Jan 18, 2022·

Subscribe to our newsletter and never miss any upcoming articles

• Problem Statement
• Solution

## Problem Statement

Given a non-empty array of integers `nums`, every element appears twice except for one. Find the element which appeared once in the array.

Example 1

``````nums   = [1, 1, 9, 9, 2, 2, 3]
output = 8
``````

Example 2

``````nums   = [1, 2, 2, 3, 3, 1, 5, 8, 5]
output = 8
``````

Example 3

``````nums   = [-12, 23, 23, -8, -12, 0, 0]
output = 8
``````

Constraints:

• 1 <= nums.length <= 3 * 100
• -3 100 <= nums[i] <= 3 100
• Each element in the array appears twice except for one element which appears only once.

## Solution

### Brute Force Solution

Simple logic to solve this problem is to use nested loops and check if every element exists twice. Here's the pseudo-code of the solution using a nested loop.

``````FOR i=0 to len(nums) :

notFound = true

FOR j=0 to len(nums):

IF nums[i] == nums[j] and i != j:
notFound = false

IF notFOund :
return nums[i]
``````

In the worst-case condition, the Runtime complexity of the above approach would be O(N^2) and space complexity would be O(1). You can find the golang implementation of above here

### Optimized Approach I

We can improve the run time complexity if we can keep the count of all the elements encountered in the `nums` array. We can keep the count using two different data structures, i.e, Array and Hash Map

• Array : Since, Elements of `nums` array lies between, `-300 to 300`, We can create array of size `601` and store counts in the array. For example `-300` at `countArray`, `-299` at `countArray`, `-298` at `countArray` and so on.
• Hash Map: We can store the elements as the key of the map and the count of the element as the value of the map.

Pseudocode (Using Array)

``````INT countArray

FOR each element in nums:

currElement = nums[i]
countArray[currElement+300] += 1
//need to add the offset 300 so that -300 maps to index 0

FOR index 0 to 601:

IF countArray at index == 1:
//need to subtract the offset 300 so that we can retrieve the correct element.
return index-300
``````

Pseudocode (Using Hash Map)

``````MAP countMap[INT]INT

FOR each element in nums:
countMap[element] += 1

FOR each element in nums:
count = countMap[element]

IF count == 1:
return element
``````

Using the above two approaches we can reduce the runtime complexity of the solution to O(N). The above approach is reducing the time complexity but it will increase the space complexity of the solution. Since we are using extra space to create a map/array, which will store N/2 elements.

### Optimized Approach II

Although we improved the runtime complexity of our code in our previous approach, we had to use extra space.

We can further optimize the code by using the XOR operation between all the elements.

XOR is boolean operator which return 0 if the we perform XOR with number itself, i.e, 5 ^ 5 => 0.

You can find more about XOR operator from Binary Operators in Golang

We can XOR all the elements of the array with itself, all the duplicate elements will result in 0 after the XOR operation, At the end, we will get the number that occurred only once.

Explanation

``````1   nums = [2,3,4,5,6,2,3,4,5]
2
3   result = 0
4   result = 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 2 ^ 3 ^ 4 ^ 5
5
6   result = (2 ^ 2) ^ (3 ^ 3) ^ (4 ^ 4) ^ (5 ^ 5) ^ 6
7   result =    0    ^    0    ^    0    ^    0    ^ 6
8   result =    0 ^ 6
9   result = 6
``````

Let's say we have nums array `[2,3,4,5,6,2,3,4,5]`, we start taking XOR of each element in the array in line `4`. As we can see in line `6`, If we just re-arrange the elements we will get 0 as a result of all the XOR operations except for the element which is occurring once. Since `0 ^ X` will always return X. We can surely say that the result variable will store the number which only occurred once

Pseudocode (Using XOR)

``````result = 0

FOR each number in nums:
result = result XOR number

return result
``````

Here's the Golang implementation of the above pseudo-code:

``````
func singleNumber(nums []int) int {

var result int

for _, num := range nums {
result = result ^ num
}

return result
}
``````

You can find the complete code here