Frontend School

Missing Number in Sequence

DSA
easy

Missing Number in Sequence

Easy
Bit Manipulation
Arrays
Math

Overview

In many data processing and communication systems, maintaining the integrity and completeness of numerical sequences is paramount. Whether it's tracking packets in a network, managing database records, or processing sensor data, missing elements can lead to system failures or incorrect results. This problem challenges you to identify a single missing number from an otherwise complete sequence using an efficient bitwise approach.

What you need to do / Task

Implement a function findMissingNumber that takes an array nums containing n distinct numbers. These numbers were originally part of a sequence that included all integers from 0 to n (inclusive). Exactly one number from this original sequence is missing in nums. Your task is to identify and return that missing number.

Input & output

  • Input: nums - An array of n distinct integers.
  • Output: The single integer that is missing from the sequence 0, 1, ..., n.

Clarifications

  • The input array nums will always contain n distinct numbers, implying that its length (nums.length) is exactly n.
  • The original sequence from which a number is missing is 0, 1, ..., n where n is nums.length.
  • The missing number can be 0 or n itself.

Examples

1

Example 1

Input:

nums = [3,0,1]

Output:

2

Note:

The array has length 3, so n=3. The expected numbers are 0, 1, 2, 3. The number 2 is missing.

2

Example 2

Input:

nums = [0,1]

Output:

2

Note:

The array has length 2, so n=2. The expected numbers are 0, 1, 2. The number 2 is missing.

3

Example 3

Input:

nums = [9,6,4,2,3,5,7,0,1]

Output:

8

Note:

The array has length 9, so n=9. The expected numbers are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. The number 8 is missing.

Constraints

Constraints & assumptions

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= nums.length
  • All numbers in nums are unique.
  • Only one number is missing.

Out of scope

  • Handling cases where multiple numbers are missing.
  • Handling non-integer inputs or negative numbers.
  • Validation of input array properties (e.g., uniqueness, range adherence).

What interviewers evaluate

  • Correctness and elegance of the bit manipulation logic.
  • Efficiency of the solution in terms of time and space complexity.
  • Clarity of code and ability to handle edge cases.
  • Ability to clearly articulate the solution's reasoning and properties.

Loading editor...