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

4578 Solutions
2484 Solvers

Last Solution submitted on Aug 05, 2020

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

Solution 2288134

1 Comment

1 Comment

Ali Osman Üstünel on 17 May 2020

good

Solution 727419

1 Comment

1 Comment

Peng Zhiyun on 2 Sep 2015

though I did not understand the question...

Solution 449250

1 Comment

1 Comment

Alexander Razmyslov on 26 Mar 2015

Very nice solution without for loop

Solution 267741

1 Comment

1 Comment

Preeyanka on 26 Jun 2013

Problem isn't robust to direction of vector

Solution 156433

1 Comment

1 Comment

Claudia on 16 Nov 2012

Genius!

Solution 137317

2 Comments

2 Comments

Sebastian on 8 Sep 2015

Nice explanation. I just derivated the formula from the solution ;-)

Jiawei Gong on 19 Feb 2020

Thanks for the explanation.

Problem Recent Solvers2484

Problem Tags

iteration matlab

Problem 46. Which doors are open?

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers2484

Suggested Problems

More from this Author95

Problem Tags

Problem 46. Which doors are open?

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers2484

Suggested Problems

More from this Author95

Problem Tags

Players