Solving in the Lonely Integer Problem in Swift

February 19, 2019

Suppose you have an array of elements (integers), each element in the array occurs twice in the array except for one. How would you find that one element?

Constraints:

O(n) Complexity

O(1) Space (Means no Dictionaries/HashMaps!)

Bonus: Can you do it in one line?

Solution

/// Lonely Integer Problem
let array = [9, 1, 2, 3, 2, 9 ,1, 7, 7]

/// Find the number that only occurs once in the array.
func lonelyInteger(in array: [Int]) -> Int {
    // Use bit manipulation! 
    return array.reduce(0) { $0 ^ $1 }
}

print(lonelyInteger(in: array)) // 3