This is a very common interview puzzle. The problem is very simple if you understand it. So the point to note is, do not arrive at the solution so "fast”, if you are asked this puzzle in an interview and if you are not planning to show any acquaintance with this puzzle.
Problem goes like this :
There are N doors in a row numbered from 1 to N. Initially all are closed.
Then you make N passes by the N doors. In pass 1 you toggle the all the doors (1,2,3,4....)starting from the first door. In the second pass you toggle every second door(2,4,6,8,...). In the third pass you toggle all third doors(3,6,9...).Similarly you make N passes.
Question is what is the state of door k after N passes.
This is a simple but requires clear mathematical Logic.
Normally asked version has N=100.
Subscribe to:
Post Comments (Atom)
30 comments:
A common hasty answer is "all primes" but no.
Clearly the state depends on whether it got acted on an odd number of times or even number of times. If a number has odd number of factors then its open or else its closed.That property is true for squares. Lets assume
there is a factor x for k,then there has to be a y such that
k = x*y .So there is a pair for each factor and hence the number of factors is even because they can be grouped in pairs, except when x=y which means k is a perfect square.
If you want to get more mathematical then for any number N
where
N= a^p * b^q *c^r ....
where a,b,c are its prime factors
then total number of factors is
(p+1)(q+1)(r+1)...
Typically for this product to yield in an odd number means that all of p,q,r have to be even and hence it means that N is a perfect square.
The answer to this problem, is to realize, how many number will divide K. Simply it is the number of divisors of K which can be computed easily and efficient.
One easy way is to draw a NxN matrix.Let's have N=10. We can later generalize this to N=100. We find that when N=1,4,9 the door is closed. So by induction we can prove door is closed for all N=1..100 where N is a perfect square. So if K=perfect square, door is closed. if not, door is open.
@ vijeya shobana
ur sol is not perfect, lets take example of 6, it vl affected by 1 , 2, 3 and 6th iteration n finally it vl be closed. but it is not a perfect square...
Vijeya's solution is inverted. The perfect squares are the only integers where the number of factors will be odd, because the square root is "doing double duty" as a factor, and all other factors pair up. So perfect squares will be OPEN (initial state was closed) and all others are closed.
Solved in O(√n) for all doors with C# source code..
I guess this can be solved this way. K <= N. So after kth pass, door k won’t be affected anymore. So we can leave out all the passes > k. And then k will toggled on all the factors of k.
So this can be easily summarized with:
+1 – Initial state.
-1 – Toggled sate.
After kth iteration door status = (-1)^(#factors).
(no of factors will include 1 and itself).
The Perfect square door is only open.
for example in 100
1,4,9,16,25,36,49,64,81,100
There are 3 possibilities in any number set - prime numbers, non-prime numbers (that are not squares) & squares.
In this puzzle the original state of a door will be reversed if it is acted upon an odd number of times - otherwise the original state & the final state will be the same. Now let us take each of the number types I mentioned above.
1. Prime numbers are divisible by themselves & 1 - so they will be acted upon an even number of times. So these doors (corresponding to prime numbers) will be closed
2. Non-prime non-square numbers are divisible by themselves, 1, & any other two numbers such as a*b where a is not equal to b. Thus they are divisible at least by 4 numbers - which means these doors will be closed as well.
3. Square numbers are divisible by themselves, 1 & its factors a*a. Since the factors are the same, these numbers are divisible by at least 3 numbers - hence these doors will be open
In the above even if we drill down to the divisibility of a & b - we will see that each of them can be treated the same way as explained above.
if sqrt(k) is integer.
Door'K' is open
if sqrt(k) is floating point.
Door'K' is Closed.
Of course the answer is that if k is a perfect square the door is open, because only perfect squares have an odd number of factors. My daughter had this problem in the 6th grade. I have given it to quite a few computer professionals and mathematicians, and they have not done very well!
Solution is goes like this:
!(....!( !( !(k%p1)^!(k%p2) )^!(k%p3) )..........^(k%pn))
Note: there are n parenthesis in left side before starting of first logical expression k%p1.
0: close state
1: open state
!: logical negation
k: kth door number
Pi: ith pass
here k%Pi is either 0 or non zero integer, lets assume 0 means false and non zero means true.
If ith pass toggles the kth door than k%Pi must be zero
Than above mathematical logical expression represents the state of kth door after nth pass.
The solution what I think is:
Lets take a case where, what's the state of the door 6 after 5 passes - 1. First get the multiples of 6
2. If the numbers that came out in step 1 is even then the door is closed, else its open
Try this out with any number, it comes out right.
one more thing to add, posted too soon - This is valid when the door number <= Pass number.
Ahh going to solve this now...
by
Tennis Guy
For more interview puzzles check techinterviewpuzzles.com
Hi I got inspired by your blog and created my own puzzle blog
Brain Teasers
Then you make N passes by the N doors. In pass 1 you toggle the all the doors (1,2,3,4….)starting from the first door. In the second pass you toggle every second door(2,4,6,8,…). In the third pass you toggle all third doors(3,6,9…).Similarly you make N passes.
www.electrocomputerwarehouse.com
thank you for your sharing! it is really interesting!@ apple a1185 battery
Its really a nice and interesting post. Keep it up.
Generic Viagra
For example, after the first pass every door is open. on the second pass you only visit the even doors (2,4,6,8…) so now the even doors are closed and the odd ones are opened. the third time through you will close door 3 (opened from the first pass), open door 6 (closed from the second pass), etc..
question: what state are the doors in after the last pass? which are open which are closed?
solution: you can figure out that for any given door, say door #42, you will visit it for every divisor it has. so 42 has 1 & 42, 2 & 21, 3 & 14, 6 & 7. so on pass 1 i will open the door, pass 2 i will close it, pass 3 open, pass 6 close, pass 7 open, pass 14 close, pass 21 open, pass 42 close. for every pair of divisors the door will just end up back in its initial state. so you might think that every door will end up closed? well what about door #9. 9 has the divisors 1 & 9, 3 & 3. but 3 is repeated because 9 is a perfect square, so you will only visit door #9, on pass 1, 3, and 9… leaving it open at the end. only perfect square doors will be open at the end.
Very true vemana......in second case state of the door depends on whether no. is even or odd....try it
Very true vemana......in second case state of the door depends on whether no. is even or odd....try it
Very true vemana......in second case state of the door depends on whether no. is even or odd....try it
This can be solved simply by,
Consider n = total number of doors
k = door's state to find
bool DoorOpen = false;
for(int i = 1 to k)
{
if((k % i) == 0) then DoorOpen = !DoorOpen
}
From 1st to k th position we need to divide the k with i. If i is divisible with no remainder then toggle the door otherwise simply ignore
Solve this puzzle of squint eyed people.?
puzzle
Post a Comment