An array contains all the integers from 0 to n, except for one number which is missing.
Write code to find the missing integer. Can you do it in O(n) time?Example 1:
Input: [3,0,1]
Output: 2Example 2:
Input: [9,6,4,2,3,5,7,0,1]
Output: 8
XOR All Numbers Algorithm
If we XOR all numbers and also 0 to N, we will get zero (Same Number XOR twice is zero). So, if only one number is missing, The XOR value will be the missing one. The time complexity is O(N) and space complexity is O(1) constant.
1 2 3 4 5 6 7 | class Solution: def missingNumber(self, nums: List[int]) -> int: x = len(nums) for i, j in enumerate(nums): x ^= i x ^= j return x |
class Solution:
def missingNumber(self, nums: List[int]) -> int:
x = len(nums)
for i, j in enumerate(nums):
x ^= i
x ^= j
return xMath Algorithm to Find Missing Number by Sum
We know the sum from 1 to N, and if we subtract each numbers in the array, we know the missing number.
1 2 3 4 5 6 7 | class Solution: def missingNumber(self, nums: List[int]) -> int: n = len(nums) s = n * (n + 1) // 2 for i in nums: s -= i return s |
class Solution:
def missingNumber(self, nums: List[int]) -> int:
n = len(nums)
s = n * (n + 1) // 2
for i in nums:
s -= i
return sThe Time Complexity is O(N) and the space complexity is O(1) constant.
–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
283 wordsloading...
Last Post: Teaching Kids Programming - Algorithms to Check Integer Power of Three
Next Post: Teaching Kids Programming - Algorithms of Power of Two
