Question

can any one get me the logic or the code for this

Given an array of size n. It contains numbers in the range 1 to n. Each number is present at least once except for 2 numbers. Find the missing numbers.

Answer 1

Well, given that all the numbers are integers, all you need to do is create a new array with [1, 2, 3, ..., n]. Then go trough the original array deleting the matching place in the new array. Once the loop is done, you are left with the new array that contains the missing numbers.

Answer 2

cool solution but this will take O(n^2) .. can we reduce it to O(n)...?

Answer 3

No. I don't think that's possible. What you can do though is instead of making a new array, just find each number 1 to n from the array and whether it exists.

Answer 4

if u want int O(n) here u go:

create a new array of size n with all value in zero an call it sums or wahateve u want

then loop the array u go doing this

for(i = 0; i < n ; i++)
sums[array[i]]++;

then

for(i = 0; i < n ; i++)
if(sums[i] == 0)
pirint "The number " + i " is missing."

So u go n + n + n wich is O(3n) and linear, maybe u can get a better solution, but this one works and its easy to understand.

Answer 5

Wow this is a cool solution, thanks a lot :) :)