Puzzle: :
You have 100 doors in a row that are all initially closed. you make 100 passes by the doors starting with the first door every time. the first time through you visit every door and toggle the door (if the door is closed, you open it, if its open, you close it). the second time you only visit every 2nd door (door #2, #4, #6). the third time, every 3rd door (door #3, #6, #9), ec, until you only visit the 100th door.
What state are the doors in after the last pass? Which are open which are closed?
Puzzle asked in: Google/Adobe/Amazon/Oracle
Puzzle Solution:
You can figure out that for any given door, say door #38, you will visit it for every divisor it has. so has 1 & 38, 2 & 19. so on pass 1 i will open the door, pass 2 i will close it, pass 19 open, pass 38 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.
no, u have to read the qustion for the initial condition weather the gates r closed or open,. in this qustion the gates r initially closed if gates r initially open the answer is opposite
We can calculate the no. of factors for each numbered door. For all those doors which have odd number of factors will be open and for all those which have even no. of factors will be closed.
so 1,4,9,8,12,… will be open
2,3,5,6,7,10,11,… closed
Please let me know any suggetsions
only perfect squares have odd no. of factors, and every other number has even of factors.
so the doors numbered 1,4,9,16,25,36,49,64,81,100 will be different from initial from position.
other numbered doors will be the same as in beginning
8->1,2,4,8 (even no of factors)
12->1,2,3,4,6,12(even no of factors)
Its a concept that only perfect squares have odd no of factors that we can keep in our memory for future use.
Bingo.. Yes These puzzles are just to realise us the concept.. Thanks for sharing this
I have post the c code. You can compile it with dev-c++;
Final output is
100100001000000100000000100000000001000000000000100000000000000100000000000000001000000000000000000
//You have 100 doors in a row that are all initially closed.
//you make 100 passes by the doors starting with the first door every time.
//the first time through you visit every door and toggle the door
//(if the door is closed, you open it, if its open, you close it).
//the second time you only visit every 2nd door (door #2, #4, #6).
//the third time, every 3rd door (door #3, #6, #9), ec, until you only visit the 100th door.
//What state are the doors in after the last pass? Which are open which are closed?
//0 means close and 1 means open
#include
void main (void)
{
int num,i,j;
num=100;
int ans[num];
//initialize
for(i=0;i<(num-1);i++)
{
ans[i]=0;
}
//iterations j=nº travel i=nºdoor
for(j=0;j<(num-1);j++)
{
for(i=0;i<(num-1);i++)
{
//if remainder is 0
if((i+1)%(j+1)==0)
{
//bit toogle
if(ans[i]==0)
{
ans[i]=1;
}
else
{
ans[i]=0;
}
}
}
}
//show by screen
for(i=0;i<(num-1);i++)
{
printf("%d",ans[i]);
}
}
Thanks guillem for programming solution.
thanks guillem for the post…
helpful….
Here is the java code for this
package javaPractise;
public class DoorOpen {
public static void main(String[] args) {
// TODO Auto-generated method stub
int length=101;
int arr[]=new int[length]; // by default all doors are closed . Lets assume
System.out.println(“0 is closed”);
System.out.println(“1 is open”);
for (int i=1;i <length; i++)
{
// System.out.println();
for(int j=i; j<length && j<=100; j=j+i)
{
// Lets revert the condition on each pass , if o(closed) then 1(open) and vice versa
if(arr[j]==0)
{
arr[j]=1; // door is open now
}
else if(arr[j]==1)
{
arr[j]=0; // Door is closed
}
}
}
System.out.println(" The below doors are open");
for (int i=1;i <length; i++)
{
if(arr[i]==1)
{
System.out.println(i);
}
}
}
}
Another way to do this is by assigning numbers to closed and opened doors , this is purely logical and doesn’t require any mathematical knowledge.
Suppose we give the number 0 to all closed doors and 1 to all open doors.
When we start, all doors are closed hence
0000000000000…………..0
1st chance : we open all doors , hence the sequence will be
1111111111111…………1
2nd chance : every second door is toggled, hence :
10101010101010……..10
3rd chance : every third door is toggled, hence
100011100011….. and this goes on , as you see the sequence is repetitive with the group 100011 occurring again and again , as 100011 comprises of 6 digits, the 97th number to 102th number would be 100011, making the 100th door a 0 which means it is closed.
I hope this helps
l= [0]*int(input())
for i in range(1,len(l)+1):
for j in range(0,len(l),i):
if l[j]==0:
l[j]=1
else:
l[j]=0
print(l.count(1))
l=[]
close=’c’
open=’o’
for i in range(1,101):
l.append(close)
print(l);
for i in range(1,101):
for j in range(0,100,i):
if l[j]==close:
l[j]=open
else:
l[j]=close
print(l)
int []doors = new int[100];
for(int i=0;i<doors.length;i++) {
doors[i] = 0;
}
for(int i=0;i<doors.length;i++) {
for(int j=i; j<doors.length;j=j+i+1) {
if(doors[j]==0)doors[j]=1;
else doors[j]=0;
}
}
for(int i=0;i<doors.length;i++) {
if(doors[i]==1)
System.out.println(doors[i]+" , "+(i+1));
}
The ans would be 10,
Ruby code to solve this:
“`
LEN = 100
array = [false] * LEN
(1..LEN).each do |x|
(-1..LEN).step(x).each do |i|
next if i == -1
break if i >= LEN
array[i] = !array[i]
end
end
array.count{|x| x}
# => 10
“`
in C#
public static void OneHundredDoors()
{
bool[] doors = new bool[100];
for(int round=1; round<=100;round++)
for(int i= round-1; i<100;i+=round)
doors[i] = !doors[i];
for (int i = 0; i < 100; i++)
if(doors[i])
Console.WriteLine(string.Format("Door {0} is Open",i+1));
}
results:
Door 1 is Open
Door 4 is Open
Door 9 is Open
Door 16 is Open
Door 25 is Open
Door 36 is Open
Door 49 is Open
Door 64 is Open
Door 81 is Open
Door 100 is Open