🧩 Problem Statement (LeetCode 268)
You are given an array containing n distinct numbers taken from the range 0 to n.
Return the one number that is missing from the array.
🧠 Example:
Input: [3, 0, 1]
Output: 2
✅ Swift Solutions
🔹 1. Using Sum Formula (O(n) time, O(1) space)
func missingNumber(_ nums: [Int]) -> Int {
let n = nums.count
let expectedSum = n * (n + 1) / 2
let actualSum = nums.reduce(0, +)
return expectedSum - actualSum
}
🧠 Explanation:
The sum of numbers from 0...n is n(n+1)/2.
Subtract actual array sum from expected sum to get the missing number.
🔹 2. Using XOR (No Extra Space, O(n) time)
func missingNumber(_ nums: [Int]) -> Int {
var result = nums.count
for (i, num) in nums.enumerated() {
result ^= i ^ num
}
return result
}
🧠 Explanation:
XOR all indices and values; missing one will cancel out and remain.
🔹 3. Using Set (Extra Space O(n))
func missingNumber(_ nums: [Int]) -> Int {
let set = Set(nums)
for i in 0...nums.count {
if !set.contains(i) {
return I
}
}
return -1
}
✅ Example Call:
let arr = [0, 1, 3]
print(missingNumber(arr)) // Output: 2
Top comments (0)