Problem 46. Which doors are open?
There are n doors in an alley. Initially they are all shut. You have been tasked to go down the alley n times, and open/shut these doors in a particular manner:
- Toggle the state of each door you visit. That is, if the door is shut, open it, and if the door is open, shut it.
- On the i-th trip down the alley, start with door i and visit every i-th door.
Given n doors, return the list of open doors.
Example:
Let's say n = 3.
- On your first trip, you start from the first door and toggle every door. Now all three doors are open.
- On your second trip, you start from the second door and toggle every other door. Since there are only three doors, this means you shut the second door. Now doors 1 and 3 are open.
- On your third trip, you start from the third door and toggle every third door. Now only door 1 is open.
So:
Input n = 3 Output y is 1
Solution Stats
Problem Comments
-
9 Comments
The description does not match the example: The point 3 should be "3. On the # trip down the alley, start with door # [and process every #-th door]".
I agree with Jan - the description is not clear. The final instruction should be "return the list of open door #'s", presumably.
If the description was clearer, I'd give this problem a "like", because a good solution depends on a good analysis of the problem more than on just neat coding.
Sorry about the confusion. I tried to clarify the problem description.
Nice problem! The explicit solution was very surprising to me once I found it.
Classic problem--unfortunate that the test suite reveals the punchline.
Yes I initially thought y = sum(open doors)
good problem, easy solution once realising how to solve
easy if to think a bit
Solution Comments
Show commentsProblem Recent Solvers3298
Suggested Problems
-
2034 Solvers
-
516 Solvers
-
302 Solvers
-
737 Solvers
-
1657 Solvers
More from this Author96
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!