How to Find the Unique Number in O(n) Time Using XOR in Go

Problem Description

Given an array of integers where every value appears exactly twice except one value that appears once, find the unique value.

Analysis

The array length is odd. An O(n) time algorithm with O(1) extra space is required.

Solution Using XOR

Properties of XOR

Commutative : a ^ b = b ^ a Associative : (a ^ b) ^ c = a ^ (b ^ c) Identity : a ^ 0 = a Self‑inverse : a ^ a = 0 Because identical numbers cancel out, XOR‑ing all elements leaves the single non‑repeating number.

Algorithm Steps

Initialize result = 0.

Iterate over the array and update result ^= element for each element.

After the loop, result holds the unique number.

Complexity

Time : O(n) – each element is processed once.

Space : O(1) – only the variable result is used.

Go Implementation

package main

import "fmt"

func findUniqueNumber(nums []int) int {
    result := 0
    for _, v := range nums {
        result ^= v
    }
    return result
}

func main() {
    samples := [][]int{
        {1, 1, 2, 2, 3, 3, 4, 5, 5},
        {0, 1, 0, 1, 2},
        {7, 3, 3, 7, 10},
    }
    for _, s := range samples {
        fmt.Println(findUniqueNumber(s))
    }
}

Explanation

findUniqueNumber

traverses the slice and accumulates the XOR.

The main function demonstrates three test cases.

Test Cases

Input: [1,1,2,2,3,3,4,5,5] → Output: 4 Input: [0,1,0,1,2] → Output: 2 Input: [7,3,3,7,10] → Output:

10

UML Activity Diagram

The algorithm can be visualized with an activity diagram showing initialization, loop, and return.

Conclusion

The XOR‑based method finds the single non‑repeating integer in linear time and constant space, satisfying the problem constraints.