[Leetcode/Python] Missing Number

Top Interview Questions 의 Easy Collection에 있는 문제입니다.         
문제는 여기서 볼 수 있습니다.

 

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

 

Example 1:

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Example 2:

Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Example 3:

Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

 

Constraints:

• n == nums.length
• 1 <= n <= 10^4
• 0 <= nums[i] <= n
• All the numbers of nums are unique.

 

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

 

- 수학적으로 풀면 시간과 공간복잡도를 크게 줄이며 풀 수 있습니다.

- 리스트 nums에는 0~n까지의 n+1개 숫자들 중 n개를 중복없이 포함한 리스트입니다. 따라서 0~n까지의 숫자 중 포함되지 않은 수 하나를 리턴하면 되는 문제입니다.

 

1. n (= nums.length)를 구해 m이라는 변수를 초기화합니다.

2.  0~n의 수를 모두 더한 값(m*(m+1)//2)에서 입력으로 주어지는 리스트 nums 내 값들의 합(sum(nums))을 빼면 어떤 수가 빠졌는지 알 수 있습니다.

(3. 2번의 결과가 0일 때는 리스트 nums 에서 빠진 수가 0일 경우이므로 0을 리턴하는 것이 맞습니다. 따라서 신경쓰지 않아도 됩니다.)

 

Code:

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        m = len(nums)
        return m*(m+1)//2 - sum(nums)

해당 문제 결과(UI가 너무 이뻐진 리트코드..)

수학적으로 풀 수 있다면 그렇게 푸는 것이 풀이가 훨씬 간단해지고 복잡도도 낮아지는 것 같다.

대개 수학적으로 풀리는 문제가 어렵다는 것이 문제지만.....ㅎㅎ 이 문제는 큰 어려움 없었다.