Coding Task in Swift. Find odd occurring number in array

Task: Given an array of of repeating integer numbers. All numbers are repeated an even number of times, except for one. Find that odd occurring number.

Solution with two for loops

Example of an array, there is one odd occurring number, it is 9.

let array = [1, 2, 3, 9, 3, 2, 1]

Algorithm is following:

1. Create dictionary (hash table) with keys of type Int and values of type Int. Key is number itself, value is counter of this number.
2. First for loop. For each number in array
• If number already exist in dictionary then increment counter for this number by 1
• Else add this number to dictionary as key and assign value of 1 to this number
3. Second for loop. For each key/value pair in dictionary
• If the value is odd (remainder of division by 2 is not 0) then return key (key is the number)
4. By default return nil from function. So function will return type optional type Int?

func findOdd1(_ array: [Int]) -> Int? {
    var table = [Int: Int]()
    array.forEach {
        if let count = table[$0] {
            table[$0] = count + 1
        } else {
            table[$0] = 1
        }
    }
    for pair in table {
        if pair.value % 2 != 0 {
            return pair.key
        }
    }
    return nil
}

There are two for loop for N elements, so time complexity for each will be 0(n). It will give us O(n) + O(n) that equals to O(2n) that equals to O(n) because we can drop coefficients when estimate the complexity.
Get result and check for errors

findOdd1(array) // 9
assert(findOdd1(array) == 9, "Error happened")
// Time Complexity is O(n) + O(n) because of two for loop,
// but it gives O(2n) that is equivalent to O(n)

Optimised Solution

There are ways to modify and optimize first solution. When we iterate over elements in array we can check if number occur even number of times we can remove it from dictionary. So as result we will have in dictionary only numbers that occurred odd number of times. Here we have only one such number in array, so we return first key from dictionary.

// Optimised solution
func findOdd2(_ array: [Int]) -> Int? {
    var table = [Int: Bool]()
    array.forEach {
        if table[$0] != nil {
            table[$0] = nil
        } else {
            table[$0] = true
        }
    }
    return table.keys.first
}

There is only one for loop over n elements is array. So time complexity will be O(n)
Get result and check for errors

findOdd2(array) // 9
assert(findOdd2(array) == 9, "Error happened")
// Time Complexity is O(n) - we remove one for loop.

Source Code

Source code can be found here on GitHub