2dbi
Home/Oracle/Missing Number in an Unsorted Array
OOracle·DSASDE-2Onsite – Coding 1

Missing Number in an Unsorted Array

Problem

Given an array containing n distinct numbers in [0, n], find the one that is missing.

Example

[3,0,1] -> 2

Constraints

  • 0 ≤ n ≤ 10^4

Approach

Sum formula n(n+1)/2 - sum, or XOR trick. Discuss overflow safety.

added 6 days ago
LeadersAccount