Missing two numbers in array
An array contains all the integer from 0 to n, expect for two numbers which are missing. Find missing number in O(n) in O(1) extra space.
Facts:
- Find missing numbers sum
- Find missing numbers product
- Suppose missing numbers are x and y.
- Now, x + y = sum_of_missing_numbers and
- x * y = product_of_missing_numbers
- Solve this quadratic equation.
Algorithm:
- Compute sum_of_missing_numbers
- Computer product_of_missing_numbers
- Set a = 1, b = sum_of_missing_numbers and c = product_of_missing_numbers
- Now Solve ax^2 + bx + c = 0
- Missing number1 = (-b+√(b2−4ac)) / 2a
- Missing number2 = (-b-√(b2−4ac)) / 2a
- Return number1 and number2
Latest Source Code:
Github: MissingTwoNumbersInArray.java
Output:
Array: [1, 2, 4, 6, 5] N: 7 Missing Number: Missing Numbers {n1=-3, n2=-7}