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 Solvers3280
Suggested Problems
-
1896 Solvers
-
Given two arrays, find the maximum overlap
1490 Solvers
-
477 Solvers
-
Find the index of the largest value in any vector X=[4,3,4,5,9,12,0,4.....5]
374 Solvers
-
Natural numbers in string form
1394 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!