Login/RegisterInterview Puzzles :: Discussion
-
A prison has 1000 cells. Initially, all cells are marked with - signs. From days 1 thru 1000, the jailor toggles marks on some of the cells: from + to - and from - to +. On the ith> day, the signs on cells that are multiples of i get toggled. On the 1001th> day, all cells marked with + signs are opened. Which cells are these?
Explanation :
No Best Answer on this question yet!Not Yet Asked in Any of the Companies
A cell is toggled as many times as the number of divisors it has. For
example, cell number 24 is toggled on days 1, 2, 3, 4, 6, 8, 12 and 24.
Now, divisors come in pairs like 24 = 1*24 = 2*12 = 3*8 = 4*6. So the
total number of divisors is even, except when the number is a perfect
square, in which case the total number of divisors is odd. Since all
cells are initially marked with - signs, only those cells that have an
odd number of divisors have + signs eventually. These are cell numbers
1, 4, 9, 16, 25, 36, and so on.
