BL
U

38. Find Missing Number from 1 to N

Easy

Problem Description

Given an array containing N−1N-1 distinct integers from the range [1,N][1, N], find the single missing number.

Input Format

  • •Line 1: An integer NN (2≤N≤1052 \le N \le 10^5).
  • •Line 2: N−1N-1 space-separated integers.

Output Format

Print the missing integer.

Example 1:
Input:
5
1 2 4 5
Output:
3
Explanation: Numbers are 1, 2, 4, 5. Missing number is 3.
Example 2:
Input:
2
1
Output:
2
Explanation: Range is [1, 2], missing is 2.
Example 3:
Input:
4
2 3 4
Output:
1
Explanation: Missing number is 1.
Constraints:
  • Standard integer bounds: 32-bit signed integer or input range [1, 10^5].
  • Time complexity target: O(N) or O(N log N) where applicable.
  • Auxiliary space target: O(1) or minimal auxiliary memory.
Follow up:Can this algorithm be adapted to an online streaming setting where the entire input cannot be held in memory simultaneously?
1,180 Online