posted 4 years ago

There are total 50 integer nos in a bag.Starting from 1 to 50.Now lets say two random numbers are missing from the bag.

How I can find which two nos are missing.

I can solve the problem for any random single no is missing.But struck when it asked what are the two random numbers are missing..

Any idea how to do that.

How I can find which two nos are missing.

I can solve the problem for any random single no is missing.But struck when it asked what are the two random numbers are missing..

Any idea how to do that.

Kevin Florish

Ranch Hand

Posts: 182

posted 4 years ago

Well one way I can think of off the top of my head is to put the remaining numbers into an array.

Sort the array and then do a for loop (1 48) and when the increment doesn't match a number in the array (-1) you have your first number, if you don't get a mismatch then the numbers are 49 and 50.

Then reverse the array and do a for loop from 50 backwards checking against index 0, 49 against index 1 etc.

When you get a mismatch you have your second number, or if you hit index 47 and no mismatch the second missing number is 2.

...

Another way could be to make an array of size 51 and put each remaining number into array slot number +1.

Then check array and the array entries between 1 and 50 that have no values are your missing numbers.

I am sure their are more elegant solutions but I think these will work.

Sort the array and then do a for loop (1 48) and when the increment doesn't match a number in the array (-1) you have your first number, if you don't get a mismatch then the numbers are 49 and 50.

Then reverse the array and do a for loop from 50 backwards checking against index 0, 49 against index 1 etc.

When you get a mismatch you have your second number, or if you hit index 47 and no mismatch the second missing number is 2.

...

Another way could be to make an array of size 51 and put each remaining number into array slot number +1.

Then check array and the array entries between 1 and 50 that have no values are your missing numbers.

I am sure their are more elegant solutions but I think these will work.

dennis deems

Ranch Hand

Posts: 808

posted 4 years ago

You wouldn't even need to store the numbers. Just make it a boolean array and for each number encountered set the value of array[number] to true.

Kevin Florish wrote:Another way could be to make an array of size 51 and put each remaining number into array slot number +1.

Then check array and the array entries between 1 and 50 that have no values are your missing numbers.

You wouldn't even need to store the numbers. Just make it a boolean array and for each number encountered set the value of array[number] to true.

posted 4 years ago

https://www.google.com/search?q=how%20to%20find%202%20missing%20numbers%20in%20an%20array . very first url sounds Ok.

Praveen Kumar M K

Ranch Hand

Posts: 256

posted 4 years ago

Needless post alert

You can add all the existing numbers in the array and find the difference between that and [Summation(1-50)], and then do a full scan of the array to find the missing numbers using a little intelligence. An example here,

Say you were working with numbers 1 to 10. And the input array was like this 1, 2, 3, 4, 7, 8, 9, 10 with 5 and 6 missing (sorted/unsorted doesnt matter here).

So we have Summation(1 to 10) - Summation(input array) = 11. Now 11 can either be due to (1,10), (2,9), (3,8), (4,7) etc. Do a linear scan and and when you find a number in one of these combinations, you can eliminate that particular combination of numbers.(Also, if you find 2 in the input array you dont have to check for 9).

You can add all the existing numbers in the array and find the difference between that and [Summation(1-50)], and then do a full scan of the array to find the missing numbers using a little intelligence. An example here,

Say you were working with numbers 1 to 10. And the input array was like this 1, 2, 3, 4, 7, 8, 9, 10 with 5 and 6 missing (sorted/unsorted doesnt matter here).

So we have Summation(1 to 10) - Summation(input array) = 11. Now 11 can either be due to (1,10), (2,9), (3,8), (4,7) etc. Do a linear scan and and when you find a number in one of these combinations, you can eliminate that particular combination of numbers.(Also, if you find 2 in the input array you dont have to check for 9).

Don't get me started about those stupid light bulbs. |