100 Doors Puzzle

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

100 doors toggle puzzle

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.

15 Thoughts on “100 Doors Puzzle

  1. Abhishek Vishal on November 7, 2014 at 5:23 pm said:

    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

  2. Priyanshu on September 3, 2015 at 1:32 pm said:

    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

    • Tinkumol on September 21, 2015 at 9:29 pm said:

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

  3. guillem on April 24, 2016 at 4:47 pm said:

    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]);
    }

    }

  4. Gaurav Khurana on February 1, 2017 at 5:04 pm said:

    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);
    }
    }
    }

    }

  5. Ekaansh Chamoli on April 29, 2018 at 5:56 pm said:

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

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

  7. jaya tanwani on December 20, 2019 at 2:15 am said:

    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)

  8. Harsh Sharma on December 31, 2019 at 3:55 pm said:

    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));
    }

  9. Nimesh on April 23, 2020 at 1:11 am said:

    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
    “`

  10. Mouayad on December 18, 2020 at 4:22 pm said:

    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

Leave a Reply to guillem Cancel reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation