forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathseungriyou.py
More file actions
42 lines (34 loc) ยท 1.27 KB
/
seungriyou.py
File metadata and controls
42 lines (34 loc) ยท 1.27 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# https://leetcode.com/problems/missing-number/
from typing import List
class Solution:
def missingNumber_math(self, nums: List[int]) -> int:
"""
[Complexity]
- TC: O(n) (sum(nums))
- SC: O(1)
[Approach]
์ํ์ ์ผ๋ก ์๊ฐํด๋ณด๋ฉด, missing number๋ (0 ~ n๊น์ง ๊ฐ์ ํฉ) - (nums์ ํฉ)์ด ๋๋ค.
"""
# (sum of [0, n]) - (sum(nums))
n = len(nums)
return n * (n + 1) // 2 - sum(nums)
def missingNumber(self, nums: List[int]) -> int:
"""
[Complexity]
- TC: O(n)
- SC: O(1)
[Approach]
bit manipulation ๊ด์ ์ผ๋ก ์ ๊ทผํด๋ณด๋ฉด, missing number๋ฅผ ์ ์ธํ ๋๋จธ์ง ๊ฐ์ ๋ค์ ๋ ๊ฐ์ง ๊ฒฝ์ฐ์์ ๋ชจ๋ ๋ฐ๊ฒฌ๋๋ค.
(1) 0 ~ n๊น์ง์ ๊ฐ
(2) nums์ ์์
missing number๋ ์ด ๋ ๊ฐ์ง ์ผ์ด์ค ์ค (1)์์๋ง ํ ๋ฒ ๋ฐ๊ฒฌ๋๋ฏ๋ก, ์ด๋ฅผ XOR ์ฐ์ฐ์ผ๋ก ๊ฒ์ถํด ๋ผ ์ ์๋ค.
(์ง์ ๋ฒ ๋ฑ์ฅํ ๊ฐ์ ์ฌ๋ผ์ง)
"""
res = 0
# (1) 0 ~ n๊น์ง์ ๊ฐ XOR
for i in range(len(nums) + 1):
res ^= i
# (2) nums์ ์์ XOR
for n in nums:
res ^= n
return res