Question

You are given a bag of numbers from 1,2,...,100, and each number appears exactly once (so there are exactly 100 numbers). TWO random numbers are removed from the bag. How would you find out what those two numbers were?

Answer 1

If theres only 1 number removed from the bag, then it's 5050 - sum(remaining numbers in the bag). What if two numbers were removed? Bonus: What if k numbers were removed from the bag?

Answer 2

this is non-trivial.

Answer 3

u knw the answers

Answer 4

actually, I dont :-P

Answer 5

Well see what numbers you removed from the bag. :P
This question does not make sense to me. :P

Answer 6

no you know answer, it's: write a python code

Answer 7

no.it is generally asked in interviews

Answer 8

agd, why don't u just explain how to solve it since u know the answers... come on now.... :) or at least explain the logic behind the solution... ;)

Answer 9

@saso I actually don't :(

Answer 10

I think mathmate is on to something :-D

Answer 11

hint: sums

Answer 12

JamesJ would solve this one in a minute with pencil and paper :-D

Answer 13

I don't have the answer, but here are some considerations.
For one number removed, you check the sum, and subtract from 5050, so that O(n) operation.
For two numbers removed, you would find the sum of the numbers by subtracting from 5050. But that would give n/2 possibilities.
Say the sum of the numbers is 8, then they could be (1,7), (2,6)...(n-1,n+1).
If we have to go through the numbers to look for one number in each pair, we have to look n/2 time, so it's an O(n^2) complexity.
It's cheaper to sort the numbers, which is O(nlog(n)).
Hope someone can do better.

Answer 14

so O(n) time to scan through the bag, noting that there are k missing elements.

Answer 15

If you know which number is possibly missing, it's O(n). If you don't know the candidates, it would be O(n^2), I think.

Answer 16

the question doesn't make sense to me, yet. Just look at the two numbers. (Are you not allowed to do that?) Or look at the leftover 98 numbers to see which are missing. (Are you not allowed to do that?)

Or look at the sum of the remaining numbers ... wait, what, how do you know their sum if you don't know them? ... and the product of the remaining numbers (are we allowed to take their product?) ... Or use the sums of their squares (can we do that?)

I'm just wondering which manipulations of the number-bag are "allowed" ... can we take their sum; partial sums; product; sums of squares; sum of all differences-squared; sum of all products; etc etc

Answer 17

http://stackoverflow.com/questions/3492302/

Answer 18

@Broken

You can scan through the the list and note which k elements are missing, but if k is large, that will consume a lot of memory!

Answer 19

imagine a bag of a billion numbers, and a random 700 million of them are missing...

Answer 20

The link makes sense.
If we are missing k numbers, we just sum x, x^2, x^3, ... x^k and end up with k equations to solve for the missing numbers. The work is O(kn)=O(n).

Answer 21

\begin{array}l\color{#FF0000}{\text{Right!}}\text{ }\color{#FF7F00}{\text{That}}\text{ }\color{#FFE600}{\text{solution}}\text{ }\color{#00FF00}{\text{works!}}\text{ }\color{#0000FF}{\text{:-D}}\end{array}

Answer 22

can you program it in a high-level language though?

Answer 23

this is a good question to annoy the CS professor :-D

Answer 24

several good answers at http://stackoverflow.com/questions/3492302/easy-interview-question-got-harder-given-numbers-1-100-find-the-missing-numbe

the code is difficult when k>3 for example

Answer 25

this question separates the IT boys from the real computer scientists.

Answer 26

ya none of the questions i've asked on OpenStudy have been solved yet :/