Friday, May 2, 2008

Door Toggling Puzzle Or 100 Doors Puzzle

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.

77 comments:

Vivek Krishna said...

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.

hitesh_sachdeva17 said...
This comment has been removed by the author.
mostafa_saad said...

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.

Vijeya Shobana said...

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.

noushy said...

@ 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...

PRN said...

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.

fe said...

Solved in O(√n) for all doors with C# source code..

Vindana Madhuwantha said...

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).

fengfk2008 said...

車燈來看看唷!
情趣用品對一般人來說充滿神秘動人的吸引力,許多人想一窺情趣用品究竟,卻又不敢太過接近,因為這個領域充斥著謠言與標籤、讓許多人深怕一碰及就會讓別人投射以異樣的眼光看待。

如果大家稍微留意一下,不難可以發現一些事,大多人在逛街時對每一間情趣用品店的櫥窗都會向內張望後姍姍離去,有一些人卻是假裝目不斜視的走過。畢竟台灣人的觀念並沒有像國外一樣的開放,所以還無法很公開與光明正大的踏進情趣用品去選購一些情趣用品
 
利用網路購物的方式去選購情趣用品是相當方便的一件事情,可以從網頁上獲得商品的詳細介紹而不必害羞的去詢問店員商品的使用方法,並且在商品的介紹上面也不亞於從店員那獲得的資訊,有些甚至還更詳細一些。
 
在台灣有許多情趣用品訂購網站,從以前只有少樣的情趣用品到今日數百種的情趣用品看來,這種促進閨房之樂的東西已經漸漸地為人們所接受與喜愛。

但以目前的市場來說,絕大部分的情趣用品網站皆以銷售台灣、大陸製造的情趣用品居多。原因很簡單:成本低廉,卻也因此犧牲了品質和安全性!情趣用品是直接與自己和最親密的另一半的身體接觸,為了節省一點點的金錢而選擇品質粗糙的廉價黑心情趣用品,實為相當不智的選擇。

我的站點介紹:情趣,情趣,情趣,情趣情趣,
情趣,
情趣,
情趣,
情趣,
情趣 來看看

a片

清境民宿優閒自得的好地方
搬家公司請找優良的
賣克
要找搬家公司要打哪隻電話
我想買一台二手車來開

Suresh Kumar said...

The Perfect square door is only open.
for example in 100
1,4,9,16,25,36,49,64,81,100

paramag said...

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.

Pankaj said...

if sqrt(k) is integer.
Door'K' is open
if sqrt(k) is floating point.
Door'K' is Closed.

David Cásseres said...

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!

AlexRayner said...

色情漫畫18x us777成人美腿性行為a片免費線上看sex888免費看影台灣情色論壇cpz無料動畫無名正妹文迪巨乳圖片辣妹聊天室辣妹合唱團色情無碼圖片老熟女清涼寫真漏毛18禁地戀愛遊戲18 c8亂倫影片免費av18禁高中正妹宅女在古代後宮的幸福生活找一夜情明星走光圖歐美猛男西洋白虎美女圖成人情色歐美素圖台中人聊天室735聊天室侯佩岑走光a圖貼圖85cc免費影片85cc無碼av女優西裝男同志交友網歐美美女遊戲世界美腿影片av女傭日本正妹比基尼小姐淫蕩人妻s級素人美女裸體a片卡通777美女dvd影片援交友留言美女影片性交

相處 said...

閒暇為所有財富中最美好的財富........................................

香覽 said...

你的部落格很棒,我期待更新喔........................................

119 said...

I love readding, and thanks for your artical. ........................................

春天來嚕 said...

IT IS A VERY NICE SUGGESTION, THANK YOU LOTS! ........................................

于名于名 said...

I love readding, and thanks for your artical.........................................

rvinder said...

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.

TommyStark0109佩政 said...

你不能改變容貌~~但你可以展現笑容......................................................

王俊貴 said...

你不能左右天氣,但你可以改變心情......................................................

鈺禎 said...

嘿,你的部落格不錯耶~~只是想跟您問聲好!!........................................

GeraldF_Rotter雅慧 said...

Actions speak louder than words. ........................................

roh0218_g said...

很用心的blog,推推哦 ........................................

佳喬 said...

愛,拆開來是心和受兩個字。用心去接受對方的一切,用心去愛對方的所有。...............................................................

登山 said...

如果,人類也像鼠輩一般,花很多時間來吃飯和睡覺,一定會改善健康。 .............................................

侯郁順 said...

北台灣視訊 情色視訊小站 拓網aio交友愛情館 情色視訊天堂 視訊聊天交友1799 壞朋友論壇一夜情視訊 0509電話視訊聊天 視訊影音聊天fm358 sex免費成人影片 sex美女視訊 彩虹頻道免費影片卡通aa片 淫蕩女孩自拍 情色文學999成人性站 免費性感影片 成人漫畫-a片天堂 免費性影片 18成人space 豆豆出租情人視訊美女 QQ美女視訊秀 kk121視訊俱樂部 gogo辣妹視訊 2sex999情人輔助品a片線上試看 1111我姊是惡魔 真愛視訊聊天室 視訊網愛聊天室網路援交168論壇 北台灣視訊交友 米克綜合論壇 aio性感辣妹34c甜心寶貝貼片 交友網 sexy girl比基尼美女 免費聊天交友mm17i sex女優王國avdvd無碼 18x us 38girl 影音視訊聊天fm358 做愛視訊聊天室 性愛教學,色情 影片 免費視訊聊天aqaq 彩虹avdvd 色咪咪貼影片 avdvd免費影片 無碼avdvd無碼卡通情色 sex movie 亞洲東洋影片sexy girl,dvd 桃園視訊t 6成人網頁 無碼影片,情色交友 後宮0204movie免費影片 嘟嘟情人色網免費線上成人影片 av片-性愛 情色影片免費觀賞0204貼圖區

CourtneyR俊 said...

真正的朋友不會把友誼掛在嘴巴上..................................................

于呈均名 said...

嗨!很喜歡來這欣賞你的作品,幫你推推推當上人氣王唷.........................

SadeRa盈君iford0412 said...

成人色情動畫色情介紹男同志色情片男同志色情影片18色情遊戲色情免費線上影色情貼圖分享色情貼圖免費看色情貼圖庫色情貼影區色情愛片色情照片免費看色情遊戲色情電影賞色情圖片色情圖貼區色情圖網站色情圖影片色情漫畫天堂色情貼無色情貼區色情貼片免費看色情免費線上影片色情言情小說色情拍貼色情相片色情美女遊戲色情做愛電影色情動慢色情情色論壇上班族聊天室 免費a片下載 6k聊天室一葉情貼圖片區

佳梅 said...

看看blog放鬆一下,工作累死了.................................................................

麗芬 said...

blog不錯唷~我會常常來看的~加油~!!

陳隆 said...

欣賞是一種美德~回應是最大的支持^^....................................................................

志穎志穎 said...

河水永遠是相同的,可是每一剎那又都是新的。.................................................................

于庭 said...

成熟,就是有能力適應生活中的模糊。.................................................................

王名仁 said...

人生是故事的創造與遺忘。............................................................

筱婷筱婷 said...

nice to know you, and glad to find such a good artical!..................................................................

雅莊王edgd春2蕙婷余惠其 said...

支持你就對了!..................................................................

Vemana said...

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.

Vemana said...

one more thing to add, posted too soon - This is valid when the door number <= Pass number.

芳容222許林堅林芳容儀 said...

憤怒,是片刻的瘋狂。..................................................

雅俊芬凱陳許 said...

下次再來希望可以看到新的作品喔。............................................................

許志宏許志宏 said...

每天都是新的心情~~希望都是好心情!!!!............................................................

楊儀卉 said...

困難的不在於新概念,而在於逃避舊有的概念。............................................................

ju吳phe宇te佳ns said...

認識自己,是發現妳的真性格、掌握妳的命運、創照你前程的根源。.......................................................

琬安琬安 said...

下次再來希望可以看到新的作品喔。..................................................................

p鄭hilli智pal堯ex said...

人生有些波折,才能有些成長,所以不論順逆,凡是成長、成功的助緣,都應該心存感激。..................................................

鄭雅雯 said...

我們能互相給予的最佳禮物是「真心的關懷」。..................................................

凱v胡倫 said...

好的開始並不代表會成功,壞的開始並不代表是失敗..................................................

凱v胡倫 said...

時時關心,時時感動。..................................................

周俊許佳蓉安 said...

美麗的事物是永恆的快樂,它的可愛日有增加,不會消逝而去................................................

蕾蕾 said...

三分之一的人生,可以決定另外三分之二的人生!!共勉哦!............................................................

思佩璇佩璇翰佩璇 said...

男女互悅,未必廝守終生,相愛就是美的。.................................................................

惠邱邱邱邱雯 said...

喜歡你的部落格,讓人流連忘返..................................................................

張王雅竹欣虹 said...

人生是故事的創造與遺忘。............................................................

佳張張張張燕張張張張張 said...

人不能像動物一樣活著,而應該追求知識和美德............................................................

8468 said...

人生中最好的禮物就是屬於自己的一部份............................................................

王辛江淑萍康 said...

初次拜訪,祝你人氣一百分

江仁趙雲虹昆 said...

生命所經歷的折磨愈多,其所產生的奮鬥力愈大。................. ................................................

Jessica said...

Barrister Global Services Scam

厦门 said...

power balance
silly bandz
Raymond Weil Watches
concord papillon
rolex datejust 36mm
wedding dresses develop quality for discerning customers and Experience the comfort, free shipping.
Buy evening dresses with a price guarantee and top rated customer service.

Bhathiya99 said...

Ahh going to solve this now...
by
Tennis Guy

Quiz Questions and Answers said...

For more interview puzzles check techinterviewpuzzles.com

lavesh said...
This comment has been removed by the author.
lavesh said...
This comment has been removed by the author.
lavesh said...
This comment has been removed by the author.
lavesh said...

Hi I got inspired by your blog and created my own puzzle blog
Brain Teasers

janny said...

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

said...

thank you for your sharing! it is really interesting!@ apple a1185 battery

jon said...

Its really a nice and interesting post. Keep it up.

Generic Viagra

nigga.me said...

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.

Urvashi Gahlot said...

Very true vemana......in second case state of the door depends on whether no. is even or odd....try it

Urvashi Gahlot said...

Very true vemana......in second case state of the door depends on whether no. is even or odd....try it

Urvashi Gahlot said...

Very true vemana......in second case state of the door depends on whether no. is even or odd....try it

Diwakar Rajendran said...

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

Jr. Williams said...

Solve this puzzle of squint eyed people.?
puzzle