# “Open and closed doors” riddle

Riddle Description:

$N$ doors are closed. In the first pass, I open all of them. In the second pass, I toggle every second door. In the third pass, I toggle every third door. I continue this until I have completed the $N$th pass. Find all the doors that will remain open after $N$ passes.

public static void printDoorsOpened(int passes)
{
HashMap<Integer, Boolean> doors=new HashMap<Integer, Boolean>();
int i = 0;
//Close all doors as default in the start
while(i < passes)
{
doors.put(i, false);
i++;
}

for(int j = 1; j <= passes; j++)
{
for(int k = j - 1; k < passes; k += j)
doors.put(k, !(doors.get(k)));
}

for(int l = 0; l < passes; l++)
{
System.out.println("The door number "+(l + 1)+" is "+(doors.get(l) == true ? "Opened" : "Closed"));
}
}


Please feel free to review it based on best practices, style and any other efficient solution, but please refrain from solely style-based reviews.

-
In general, people reviewing code will focus on those issues that are most broken in your code. If the style makes the function of the code hard to review, the style will be the focus of the review. If everything is perfect in your code, and the the only perceived issue is with your style, then again it will most likely be the target of the review. It is a good thing that your style is not completely horrible here, but nor is your code perfect. –  rolfl Aug 28 '14 at 10:20

This looks like something that can get optimized to a mathematical function.

Let's run it pass by pass and try to interpret the result.

N = 12

Doors #1 through #12

Pass 1:  1 1 1  1 1 1  1 1 1  1 1 1 //All opened
Pass 2:  1 0 1  0 1 0  1 0 1  0 1 0 //2, 4, 6, 8, 10, 12 closed
Pass 3:  1 0 0  0 1 1  1 0 0  0 1 1 //3 and 9 closed, 6 and 12 opened
Pass 4:  1 0 0  1 1 1  1 1 0  0 1 0 //4 and 8 opened, 12 closed
Pass 5:  1 0 0  1 0 1  1 1 0  1 1 0 //5 closed, 10 opened
Pass 6:  1 0 0  1 0 0  1 1 0  1 1 1 //6 closed, 12 opened
Pass 7:  1 0 0  1 0 0  0 1 0  1 1 1 //7 closed
Pass 8:  1 0 0  1 0 0  0 0 0  1 1 1 //8 closed
Pass 9:  1 0 0  1 0 0  0 0 1  1 1 1 //9 opened
Pass 10: 1 0 0  1 0 0  0 0 1  0 1 1 //10 closed
Pass 11: 1 0 0  1 0 0  0 0 1  0 0 1 //11 closed
Pass 12: 1 0 0  1 0 0  0 0 1  0 0 0 //12 closed


It's a factor detector!

It detects whether for each positive integer $N$ or lower whether its divisible an even or uneven amount of times by its possible factors.

That is, 12 can be factorized as $1\times 12$, $2\times 6$, $3\times 4$, $4\times 3$, $6\times 2$, $12\times 1$. That's even, so the door ends up at 0, which is closed. 9 can be factorized as $1\times 9$, $3\times 3$ and $9\times 1$. That's uneven, so the door ends up at 1, which is opened.

Now, for any factorization $x\times y$ of a number, there exists an inverse factorization: $y\times x$. Unless $x$ equals $y$. If that's the case, then there is no inverse factorization because the inverse is the same!

So it's a square root detector! (Any number that has a positive integer as a square root has an uneven number of factorizations, the rest have an even number).

Now, this doesn't implement the algorithm that your problem statement describes, but it does end up with the same result:

public static void printDoorsOpened(final int passes)
{
int j = 1;
for(int i = 1; i <= passes; i++)
{
if(j*j == i){
j++;
System.out.println("The door number "+i+" is Opened");
} else {
System.out.println("The door number "+i+" is Closed");
}
}
}

-
You could simplify the logic (and make it even faster), by using for (i = 1; i <= (int)Math.sqrt(passes); i++) {...print("The door number " + (i * i) + " is Open);} –  rolfl Aug 28 '14 at 11:16
The instructsion say: "find all the doors that will remain open after N passes.", just sayin... ;-) But your code is more compatible with the OP's code. –  rolfl Aug 28 '14 at 11:18
@Pimgd Well you have simplified this pure on the basis of optimizing the Algorithm which works better Space and Memory complexity wise with $O(n)$ Time complexity and $O(1)$ Space Complexity. As compared to my Time Complexity $O(n!)$ and Space $O(n)$ –  Anirudh Aug 28 '14 at 14:04
@Anirudh $O(n!)$? I disagree... you had $O(n^2)$ with extra reductions. N = 10 for instance, you'd have 10 + (10/2 = 5) + (10/3 = 3) + (10/4 = 2) + (10/5 = 2) + (10/6 = 1) + 1 + 1 + 1 + 1 = 27, not 3.8 million. –  Pimgd Aug 28 '14 at 14:07
Yeap! I think you are right. I probably made a mistake while evaluating Iterations :-] –  Anirudh Aug 28 '14 at 14:11

There is no need to use a HashMap, because you already know the number of doors from the start you can use:

boolean[] doors = new boolean[doorCount];


As a boolean[] is initialized to all false, you won't need the initialization step.

I think your method is doing too much right now, I would use a couple of different methods, such as:

public static boolean[] switchDoors(boolean[] doors)
public static boolean[] switchDoorsInRange(boolean[] doors, int min, int max) // just for the fun of it
public static void printDoors(boolean[] doors)


Note that switchDoors calls switchDoorsInRange(doors, 1, doors.length)

When using a boolean[] doors for the doors this code:

doors.put(k, !(doors.get(k)));


can simply be doors[k] = !doors[k];

• Think about your variable names, try to avoid single character names
• Use braces with Java convention instead of C# convention

Side note:

Whether or not a door will be open or closed at the end depends on how the prime-factorization of it looks.

Consider the number $12$ for example. How to prime-factorize it?

$12 = 3*2*2$

And the door will toggle on $1, 2, 3, 4, 6, 12$.

Note that those numbers can be written as 1, 2, 3, 2*2, 2*3, 2*2*3. That's $6$ times, which means that the door will end as being closed.

Unfortunately, there is no efficient way to prime-factorize a number. What you have built here is very similar to a number sieve, but instead of removing non-primes you are toggling them. Modifying your code to be a real sieve instead would not require many changes to the code.

-
+1 on the Hashmap point. –  Anirudh Aug 28 '14 at 14:07
• Use a java.util.BitSet

• somebool == true should just be somebool, and, while we are at it, use printf. Replace:

System.out.println("The door number "+(l + 1)+" is "+(doors.get(l) == true ? "Opened" : "Closed"));


with:

System.out.printf("The door number %d is %s%n", (l + 1), doors.get(l) ? "Opened" : "Closed");


There are three well-known style guides for Java, the basic/original Java guideline (with revisions), the Google Java guideline, and the IDE (Netbeans, Eclipse, IntelliJ, etc.) formatters.

In each case, there are common themes, and you are doing it wrong.

• the opening block brace should be at the end of the previous block conditional. For example:

while(i < passes)
{
doors.put(i, false);
i++;
}


should rather be:

while(i < passes) {
doors.put(i, false);
i++;
}

• you should use braces for 1-liner statements (as recommended in all coding standards for Java, and most other languages that use braces) because over time it leads to more maintainable code, and reduces the likelihood of bugs being introduced. This:

for(int k = j - 1; k < passes; k += j)
doors.put(k, !(doors.get(k)));


should be:

for(int k = j - 1; k < passes; k += j) {
doors.put(k, !(doors.get(k)));
}

• On Code Review, and Stack Exchange in general, tabs do not format well. You use tabs. As it happens, both the official Java guidelines, and the Google Java guidelines advise spaces for indentation. I realize that people who use tabs feel it is better, and I am not arguing that you are wrong. What I am saying is that if you insist on presenting code with tabs then you can expect that other people will think your code messy, and that is your fault, not theirs.

-
Well one might use tabs for faster development, rather than going through the pain of pressing 'space' key 4 times you could say 'Tab' would work as a shortcut but you maybe right that using spaces might make it editor independent. –  Anirudh Aug 28 '14 at 13:53
@Anirudh - you are correct, and I am not doubting that, for you, tabs make sense. If it were me though, I would let my IDE auto-indent the next line for me, and I would have to press neither Tab nor Space at all, and still get it right. What I can say, is that when I copied/pasted your code, it was formatted wrong because not all editors understand tabs equally. That may be the fault of the editor, but it still makes you look bad. –  rolfl Aug 28 '14 at 13:56
Many IDEs will have a setting (on by default or not, depending on the application) which will insert spaces when you hit the [Tab] key. Many of those will also let you set the number of spaces to insert, and many will treat N spaces as a single tab character when you hit [Backspace]. While there are plenty of programmers who will happily argue on spaces-vs-tabs, the spaces-as-tabs feature of these IDEs cheerfully makes it a non-issue. –  Brian S Aug 28 '14 at 19:08

Actually it's a math puzzle that I've solved some years ago. So I know the shortcut, but if this question was asked in any interview don't try to be over-smart at first and make a gotcha' mistake.

The puzzle is about which door number has odd number of factors will be leaved as open. Only the perfect square numbers have odd number of factors. Boiling down the solution into code

    final int totalDoors = 200;
boolean[] state = new boolean[totalDoors+1]; // at first all doors are closed

for (int door = 1; door * door <= totalDoors; door++) {
state[door * door] = true;
}

for (int door = 1; door <= totalDoors; door++) {
System.out.println("Door number : [" + door + "] is " + (state[door] ? "Opened" : "Closed"));
}

-
You don't need the array anymore, at which point the code boils down to my solution. –  Pimgd Aug 28 '14 at 11:49
There's just something icky about writing boolean[] state = new boolean[totalDoors+1]; So much for the totalDoors variable. I understand that you try to avoid off-by-one errors here, but... is it worth it? Especially considering the solution by @Pimgd –  Simon André Forsberg Aug 28 '14 at 11:55
Actually I just finished my answer and saw that 3 answers were being posted. So though it looks like a copy-paste answer but truly I didn't know about other answers. –  Anirban Nag Aug 28 '14 at 12:40