Problem 46. Which doors are open?

Created by Cody Team

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>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:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>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.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>On the i-th trip down the alley, start with door i and visit every i-th door.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Given n doors, return the list of open doors.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Example:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Let's say n = 3.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>On your first trip, you start from the first door and toggle every door. Now all three doors are open.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>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.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>On your third trip, you start from the third door and toggle every third door. Now only door 1 is open.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>So:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ Input  n = 3\n Output y is 1]]></w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Solve

Solution Stats

5861 Solutions
3000 Solvers

Last Solution submitted on Sep 25, 2023

Last 200 Solutions

Problem Comments

9 Comments

9 Comments

Show 6 older comments

Jan on 27 Jan 2012

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]".

David Young on 3 Feb 2012

I agree with Jan - the description is not clear. The final instruction should be "return the list of open door #'s", presumably.

David Young on 3 Feb 2012

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.

Ned Gulley on 1 Mar 2012

Sorry about the confusion. I tried to clarify the problem description.

Mattias on 4 Jan 2015

Nice problem! The explicit solution was very surprising to me once I found it.

Michael on 9 Feb 2015

Classic problem--unfortunate that the test suite reveals the punchline.

Justin Pinkney on 28 Jan 2016

Yes I initially thought y = sum(open doors)

Jerivington on 2 Jun 2016

good problem, easy solution once realising how to solve

Sanzhar Askaruly on 17 Jun 2019

easy if to think a bit

Solution Comments

Show comments

Problem Recent Solvers3000

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 46. Which doors are open?

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers3000

Suggested Problems

More from this Author96

Problem Tags

Community Treasure Hunt

Problem 46. Which doors are open?

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers3000

Suggested Problems

More from this Author96

Problem Tags

Community Treasure Hunt

Players