Published on

# Easy: Single Number

Authors
• Name
Moch Lutfi
@kaptenupi

## Problem Statement

In a non-empty array of integers, every number appears twice except for one, find that single number.

Example 1:

_2Input: 1, 4, 6, 1, 3, 6, 3_2Output: 4

Example 2:

_2Input: 1, 9, 1_2Output: 9

## Solution

The simple solution is using a hashmap and iterate through the input:

• if number already in the hashmap, remove it
• if number is not present in hashmap, add it
• in the end, only left 1 data in the hashmap

Time and space Complexity: Time Complexity of the above solution will be $O(n)$ and space complexity will also be $O(n)$.

### Can we do better than this using the XOR Pattern?

Recall the following two properties of XOR:

• It returns zero if we take XOR of two same numbers.
• It returns the same number if we XOR with zero. So we can XOR all the numbers in the input; duplicate numbers will zero out each other and we will be left with the single number.

Try it yourself https://go.dev/play/p/XcOwP-nIMDO

## Code

_29package main_29_29import (_29 "testing"_29)_29_29func FindSingleNumber(list []int) int {_29 num := 0_29 for i := range list {_29 num ^= list[i]_29 }_29_29 return num_29}_29_29func TestLastIndex(t *testing.T) {_29 tests := []struct {_29 list []int_29 want int_29 }{_29 {list: []int{1, 4, 2, 1, 3, 2, 3}, want: 4},_29 {list: []int{1, 9, 1}, want: 9},_29 }_29 for _, tt := range tests {_29 if got := FindSingleNumber(tt.list); got != tt.want {_29 t.Errorf("LastIndex(%v) = %v, want %v", tt.list, got, tt.want)_29 }_29 }_29}

Time Complexity: Time complexity of this solution is $O(n)$ as we iterate through all numbers of the input once.

Space Complexity: The algorithm runs in constant space $O(1)$.