[Algorithm/Swift] Codility / PermMissingElem

문제

https://app.codility.com/programmers/lessons/3-time_complexity/perm_missing_elem/

풀이

배열 A에 들어간 요소들은 순차적으로 만들어진 정수이지만 랜덤의 위치를 가지고 있습니다.

다만 그중 하나의 요소가 빠져있는데 빠져있는 정수를 찾으면 됩니다.

Tip

• 빈값을 알 수 없으니까 1...N 의 합을 구하고 주어지는 배열의 합을 빼면 빈 정수를 확인할 수 있습니다.
  • 반복문으로 합해도 되지만 formula으로도 알 수 있습니다. (N * ( N + 1 ) / 2)

Code (O(N) or O(N * log(N)))

public func solution(_ A : inout [Int]) -> Int {
    
    let addedArray = A.reduce(0,+)
    let numberOfArray = A.count + 1
    let expectedNum = numberOfArray * (numberOfArray + 1) / 2

    return expectedNum - addedArray

}