Cracking The Coding Interview/Q 6.6

From Software Engineers Wiki
Jump to: navigation, search

There are 100 closed lockers in a hallway. A man begins by opening all 100 lockers. Next, he closes every second locker. Then, on his third pass, he toggles every third locker (closes it if it is open or opens it if it is closed). This process continues for 100 passes, such that on each pass i, the man toggles every ith locker. After his 100th pass in the hallway, in which he toggles only locker #100, how many lockers are open?

Answer #1

Imagine 16 bits for an example.

  • Initial state: 0000000000000000
  • 1st pass: XOR every 1 bit : XOR 1111111111111111 = 1111111111111111
  • 2nd pass: XOR every 2 bit : XOR 1010101010101010 = 0101010101010101
  • 3rd pass: XOR every 3 bit : XOR 0100100100100100 = 0001110001110001
  • and so on.

This means:

  • 1st bit: XOR once (1) = 1
  • 2nd bit: XOR twice (1, 2) = 0
  • 3rd bit: XOR twice (1, 3) = 0
  • 4th bit: XOR three times (1, 2, 4) = 1
  • nth bit: XOR (number of factors of n) = 1 if odd number of factors, otherwise 0.

In short, if n has odd number of factors, it will be open.

For numbers which are not n^2 have even number of factors because pairs of factors make up the number. For example, take the number 24. 24 has factors (1, 2, 3, 4, 6, 8, 12, 24). To make 24,

  • (1 x 24)
  • (2 x 12)
  • (3 x 8)
  • (4 x 6)

But for n^2 numbers, n doesn't a number other than itself. For example, take the number 16, which has factors (1, 2, 4, 8, 16)

  • (1 x 16)
  • (2 x 8)
  • (4)

Thus other than the perfect square numbers, other numbers have even number of factors and will be closed after all. So this problem becomes how many perfect numbers are there until 100. Largest perfect square until 100 is 10^2 = 100. So there will be 10 perfect square numbers (1^2 until 10^2).

Answer #2

Just to prove above statement is right, try following python code.

def main():
        doorList = [0] * 101
        for curPass in range(1, 101):
                curDoor = curPass
                while curDoor <= 100:
                        doorList[curDoor] ^= 1
                        curDoor += curPass
        for curDoor in range(1, 101):
                if doorList[curDoor]:
                        print("Door {} is open".format(curDoor))

main()

Following result proves that our reasoning process was correct.

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
Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox