Task description

• Notice : N is an integer within the range 0 ~ 100,000

Solution

Using a dictionary, the time complexity is O(N) .

After initializing the dictionary, find the missing element using a for loop.

import Foundation
import Glibc

// you can write to stdout for debugging purposes, e.g.
// print("this is a debug message")

public func solution(_ A : inout [Int]) -> Int {
    var dict: [Int:Int] = [:]
    var rst: Int? = nil

    for item in A {
        dict[item] = 1
    }

    for i in 1...A.count + 1 {
        if !dict.keys.contains(i) {
            rst = i
            break
        }
    }
    return rst ?? 0
}

Here is a more efficient way to solve this problem. I got this from GPT-4. By just using the equation for the sum of numbers.

sum of 1 ~ N is equal to N * (N+1) / 2.

TotalSum - ArraySum will be equal to the missing element because, as described, all elements of A are distinct.

public func solution(_ A : inout [Int]) -> Int {
    let N = A.count
    let totalSum = (N + 1) * (N + 2) / 2
    let arraySum = A.reduce(0, +)
    return totalSum - arraySum
}