Missing Number

LeetCode

Commonly asked at:Amazon Microsoft Adobe

Missing Number

Given an array containing n distinct numbers taken from the range 0..n, find the one number in that range that's missing.

Example

Input: 3 0 1 Output: 2

Approach

Cyclic sort: for value v at index i, its "correct" home is index v itself (as long as v < n). Repeatedly swap each value into its home index until every in-range value is sitting where it belongs. Then scan once — the first index whose value doesn't match the index is the missing number (or, if every index matches, the missing number is n itself). One O(n) pass to sort, one O(n) pass to scan.

Input format

Line 1: the array, space-separated

Print the missing number.

Not solved yet

Ctrl+Enter

Editor

nums = list(map(int, input().split()))
n = len(nums)
i = 0
# TODO: cyclic sort — swap each value to index == value, then scan for the first mismatch
while i < n:
    pass

nums = list(map(int, input().split()))
n = len(nums)
i = 0
# TODO: cyclic sort — swap each value to index == value, then scan for the first mismatch
while i < n:
    pass

Input (stdin)

Output

Run your code to see output here.

Isolated sandbox · not executed on your devicePowered by Judge0 CE (free, self-hosted). Runs in an isolated sandbox — not on your device.

Editor

nums = list(map(int, input().split()))
n = len(nums)
i = 0
# TODO: cyclic sort — swap each value to index == value, then scan for the first mismatch
while i < n:
    pass

nums = list(map(int, input().split()))
n = len(nums)
i = 0
# TODO: cyclic sort — swap each value to index == value, then scan for the first mismatch
while i < n:
    pass

Input (stdin)

Output

Run your code to see output here.

Isolated sandbox · not executed on your devicePowered by Judge0 CE (free, self-hosted). Runs in an isolated sandbox — not on your device.

Community Discussions

No discussions yet

Be the first to start a conversation.