/*
 268. Missing Number
 Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

 Example 1:

 Input: [3,0,1]
 Output: 2
 Example 2:

 Input: [9,6,4,2,3,5,7,0,1]
 Output: 8
 Note:
 Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

 */

class Solution {
    func missingNumber(_ nums: [Int]) -> Int {
        var x = 0
        let N = nums.count + 1
        for i in 1..<N {
            x = x ^ i
        }
        
        var y = nums[0]
        for i in nums.dropFirst() {
            y = y ^ i
        }
        
        return x ^ y
    }
}
