Easy: Single Number

Easy: Single Number

March 2, 2023

Moch Lutfi
Name
Moch Lutfi
Twitter
@kaptenupi

Problem Statement

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

Example 1:


Input: 1, 4, 6, 1, 3, 6, 3
Output: 4

Example 2:


Input: 1, 9, 1
Output: 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)O(n) and space complexity will also be O(n)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 (opens in a new tab)

Code


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

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

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