[LeedCode] 268. Missing Number

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

Missing Number - LeetCode

문제는 매우 직관적으로 이해할 수 있다. 중복이 없는 n 길이의 0~n 배열이 주어지는데, 이 중 한 숫자가 비어 있는데 이를 찾으면 되는 문제이다.

가장 단순하게는 O(n)으로 순회하면서 없는 값을 반환하면 된다.

class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for i in range(0, len(nums)+1):
            if i not in nums:
                return i
        return 0

O(1)로 풀려면, IQ테스트 같긴 하지만 0부터 n까지의 숫자가 주어진다는 점을 착안하여,1부터 n까지 더한 값과의 차를 구하면 O(1)로 풀 수 있다.

class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        return ((n * (n+1)) // 2 ) - sum(nums)