[LeetCode] 268. Missing Number

轉自LeetCode

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

For example,
Given nums = [0, 1, 3] return 2.

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

<Solution>
這題不困難，運用梯形公式就可以解了

想法如下

• 因為是 0 到 n 選 n 個數出來，所以先計算 0 到 n 的總合

• 再把總和和 array 裡面每個數相減，最後的數值就是少掉的那個

code 如下

還有一種解法，運用到的是 Single Number 的概念

想法如下

• 因為是從 0 到 n 挑 n 個數字出來，把這 n 個數字和 1 到 n 做 XOR，這樣有出現過的數字就會被消除，剩下的就是遺失的數字

• 至於為什麼是和 1 到 n 做 XOR，而不是 0 到 n，因為如果 0 是遺失的數字，那麼 1 到 n 做完 XOR，剩下來的就會是 0 了

code 如下(參考資料)
c++

kotlin