Question

How to find the missing number in a list containing numbers from 1 to n in O(1) time complexity with Swift

Answer 1

/*
The essence of O(1) space complexity is that the algorithm uses a fixed amount of memory,
regardless of input size. Time complexity here is O(n) because we must scan the array.
*/

func findMissingNumber(_ arr: [Int]) -> Int {
    let size = arr.count
    // formula for the sum of the first (size+1) natural numbers
    let expectedSum: Int = (size + 1) * (size + 2) / 2
    var actualSum: Int = 0

    for num in arr {
        actualSum += num
    }

    return expectedSum - actualSum
}

func main() {
    let arr = [1, 2, 4, 5, 6]
    let missing = findMissingNumber(arr)

    print("Missing number: \(missing)")
}

main()


/*
run:

Missing number: 3

*/

 

70+ SQL courses for beginners and professionals