문제
The list holds n distinct numbers taken from 0, 1, …, n, so exactly one number in that range is missing. Find it. (Hint: compare the expected total with the actual total.)
Implement missing_number(numbers).
Input
numbers: n distinct numbers from 0 to n.
Output
Return the missing number.
제약 조건
0 ≤ n ≤ 100,000
예시
예시 1
입력:
numbers = [3, 0, 1]
예상 출력:
expected = 2입력:
std::vector<long long> numbers = {3, 0, 1};
예상 출력:
long long expected = 2;입력:
long[] numbers = new long[] {3, 0, 1};
예상 출력:
long expected = 2;설명
n = 3, so the range is 0–3; 2 is missing.
예시 2
입력:
numbers = [0]
예상 출력:
expected = 1입력:
std::vector<long long> numbers = {0};
예상 출력:
long long expected = 1;입력:
long[] numbers = new long[] {0};
예상 출력:
long expected = 1;설명
n = 1 and the range is 0–1; 1 is missing.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
The numbers should match the full range from 0 through n except for one hole.
힌트 2
Compare what the complete range would total against what the list actually totals.
힌트 3
Watch for the case where the missing value is 0 or n.
예상 복잡도
O(n) time, O(1) extra space
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.