Find the missing number in the array >> A17.swift

A17.swift

// Problem Link: https://leetcode.com/problems/missing-number/

//Brute force approch
// TC -> O(n*n)
// SC -> O(1)

// ThoughtProces
// 1. Check every number from range [0...n] in array.
// 2. if it is not exist return that number.

func missingNumber(_ nums: [Int]) -> Int {
        
    let n = nums.count
        
    for i in 0...n {
        var found = false
        for j in nums {
            if i == j {
                found = true
                break
            }
        }
        if found == false {
            return i
        }
    }

    return -1
}


// Best Approch
// Hasing

// TC -> O(2n)
// SC -> O(N)

func missingNumber(_ nums: [Int]) -> Int {
    let n = nums.count
    
    var arr = Array<Int>(repeating: 0, count: n + 1)

    for i in nums {
        arr[i] = 1
    }

    for i in arr.indices {
        if arr[i] == 0 {
            return i
        }
    }

    return -1
}

// Optimal approch !
// TC -> O(N)
// SC -> O(1)

// ThoughtProcess
// Use the sum of natural number formaula to calculate the sum.
// And then subtract it from available array elements sum.
func missingNumber(_ nums: [Int]) -> Int {

    let n = nums.count
    var sum = 0

    for i in nums {
        sum += i
    }

    return ((n * (n + 1)) / 2) - sum
}