algorithmtime-complexity# Find the 2 removed numbers from an array of all numbers 1-n

Find the 2 removed numbers from an array of all numbers 1...n. The array order is randomized

andno hashmaps are allowed.

I got the following hints:

- Mark the 2 numbers with x and y... (But I'm not sure what to do with that)
- Maybe use the sum somehow?

At the end I wasn't told the correct solution and I still have no clue.

Of course, a O(nlogn) algorithm is easy, but the challenge asks for a O(n) time complexity.

With no hashmaps/hashsets allowed, I didn't see how to approach this. I mean, how is this possible without them?

How could we find the two missing numbers in O(n) time?

Solution

You could calculate what the sum and the sum of squares is of the given numbers, and compare that with what those sums would have been if the array would have also included the two missing values π₯ and π¦.

This gives you two equations:

- π₯ + π¦ = π
- π₯Β² + π¦Β² = π

Where π is the difference between the "expected" sum and the actual sum, and π is the difference of the expected sum of squares and the actual sum of squares.

By substituting π¦, the above can be rewritten as:

- 2π₯Β² β 2ππ₯ + πΒ²βπ = 0

The two solutions to that equation are the values for π₯ and π¦:

- π₯ = [π Β± β(2π β πΒ²)] / 2

Here is an implementation in JavaScript, where two random numbers are removed from a sequence from 1 to 20, and the algorithm retrieves the missing values (as the algorithm doesn't use the order of the input, I didn't bother to shuffle the input):

```
function createInput(n) {
const arr = [...Array(n+1).keys()]; // {0,1,...,n}
arr.shift(); // Remove 0 => {1,...,n}
for (let removals = 1; removals <= 2; removals++) {
const i = Math.floor(Math.random() * arr.length);
arr.splice(i, 1); // Remove random element
}
return arr;
}
function findXY(arr) {
const n = arr.length + 2;
// Expected sum and sumOfSquares
let sum = n * (n + 1) / 2;
let sumSquares = sum * (2 * n + 1) / 3;
// Subtract the actual sums
for (let i = 0; i < arr.length; i++) {
sum -= arr[i];
sumSquares -= arr[i] * arr[i];
}
// Solution to quadratic equation
const x = (sum - Math.sqrt(2 * sumSquares - sum * sum)) / 2;
return [x, sum - x];
}
for (let run = 1; run <= 4; run++) {
const arr = createInput(20);
console.log("input : ", ...arr);
console.log("missing: ", ...findXY(arr));
}
```

- How to generate uniformly distributed subintervals of an interval?
- Generating random number in a non-power-of-2 range from random bits
- Algorithm - Search and Replace a string
- Looking for a branchless algorithm for converting a specific set of 4-bit integers
- Different results for XIRR between Excel and ExcelFinancialFunctions 3.2.0
- Find four,whose sum equals to target
- A* algorithm can't find the goal in Python
- Efficiently getting all divisors of a given number
- Are there any existed API to split IEnumerable<T> to many Vector<T> in CSharpοΌ
- Generating all divisors of a number given its prime factorization
- Efficient way to insert a number into a sorted array of numbers?
- BFS Maximize Minimum Distance from a Monster along a path
- Is there effective algorithm that will return all different combination?
- Big O of algorithm that steps over array recursively
- Modification of Dijkstra's algorithm to make it work with negative weights and its time complexity
- Traversing/Moving over an unfolded cube
- Fibonacci Recursion using Golden Ratio(Golden Number)
- Karatsuba implementation in C
- Why is O(n) better than O( nlog(n) )?
- What is Sliding Window Algorithm? Examples?
- How to write a function to navigate through a non-binary tree?
- Evenly distribute QDate values into certain number of slots
- Find max product using divide and conqure in O(n) time
- Cache-friendly sqare matrix transposition logic issue
- Why doesn't Dijkstra's algorithm work for negative weight edges?
- Fast Convertion From Adjacency List to Edge List
- I convert ASCII words into numbers but am stuck trying to decode them. How to convert 1=a, 2=b, 28=ab etc? (psudeocode okay)
- Reversing the word order in a string in place
- Trying to make a 2x2 rubik's cube solving algorithm , how do i find the solution path (DFS)?
- question about missing element in array