268. Missing Number (easy)

 

easy Q that asks the missing number

class Solution:
    # 0~n 까지인 배열/set/dict를 만들고, nums 에 for 돌리면서 없는지 찾기
    def missingNumber(self, nums: List[int]) -> int:
        # for no in range(len(nums)+1):
        #     if no not in nums:
        #         return no

        n = len(nums)
        ex_res = (n*(n+1))//2
        tmp = sum(nums)
        return ex_res-tmp

 

At first attempt...

came up with a common ans, making the list/set/dict of n nums then comparing each with nums

Then I found theres no need for list/set/dict, Just iter n nums.

 

Finally saw an answer with O(n) time comp and O(1) space comp

Gauss' formula is it, 

calcing ex_res does take O(1) but sum takes O(n) so the time comp is O(n)