8
\$\begingroup\$

The author of my book does not release odd-numbered solutions to students, so I can't check my solutions. I was wondering if there was a better way to solve this problem without simply printing out the square roots.

Here is the question:

(Game: locker puzzle) A school has 100 lockers and 100 students. All lockers are closed on the first day of school. As the students enter, the first student, denoted S1, opens every locker. Then the second student, S2, begins with the second locker, denoted L2, and closes every other locker. Student S3 begins with the third locker and changes every third locker (closes it if it was open, and opens it if it was closed). Student S4 begins with locker L4 and changes every fourth locker. Student S5 starts with L5 and changes every fifth locker, and so on, until student S100 changes L100.

After all the students have passed through the building and changed the lockers, which lockers are open? Write a program to find your answer.

(Hint: Use an array of 100 Boolean elements, each of which indicates whether a locker is open (true) or closed (false). Initially, all lockers are closed.)

Here is my solution:

public class Main {
    public static void main(String[] args) {
        boolean[] lockers = new boolean[101];
        //Open all multiples of 1 before moving on to 2
        for (int i = 1; i < lockers.length; i++) {
            lockers[i] = true;
        }


        //open every locker for every multiple of i
        for (int i = 2; i <= 100; i++) {
            for (int j = 1; i * j <= 100; j++) {
                lockers[i * j] = (lockers[i * j] == true) ? false : true;
            }
        }

        //Display the indices of the open lockers
        for (int i = 0; i < lockers.length; i++) {
            if (lockers[i] == true)
                System.out.println("locker " + i + " is open.");
        }
    }
}
\$\endgroup\$
16
\$\begingroup\$

You are using i = 1 as a special case, when in fact that can be handled by your other code already:

for (int i = 1; i <= 100; i++) {
    for (int j = 1; i * j <= 100; j++) {
        lockers[i * j] = !lockers[i * j];
    }
}

However, to be more readable, I suggest changing the inner loop:

for (int i = 1; i <= 100; i++) {
    for (int j = i; j <= 100; j += i) {
        lockers[j] = !lockers[j];
    }
}

Now it reads as "Start j at i, repeat as long as j is less than or equal to 100, increase j by the value of i"

\$\endgroup\$
  • 1
    \$\begingroup\$ You really should suggest that they start from 0 and go to 99. Java arrays start at zero, so they are creating a 101 element array, not a 100 element array. \$\endgroup\$ – phyrfox Apr 13 '15 at 2:19
  • 1
    \$\begingroup\$ In this case I think the 101 element array is a good choice, as it improves readability. The array index can be the number of the locker instead of having to shift by 1. \$\endgroup\$ – dennisdeems Apr 13 '15 at 15:29
12
\$\begingroup\$
lockers[i * j] = (lockers[i * j] == true) ? false : true;

This line makes no sense at all. There are two red flags to me.

  1. Comparing to == true is just sort of bad in general.
  2. Using a ternary when the two possible options are false and true is always going to be unnecessary.

We can rewrite this as simply:

lockers[i * j] = !lockers[i * j];

if (lockers[i] == true)
    System.out.println("locker " + i + " is open.");

Again, using == true is problematic. lockers[i] is a boolean, so simply if (lockers[i]) will suffice. But there are other problems with this.

If you insist on omitting braces (which I can never recommend), we should move the executed line on to the same line as the if. This makes it less likely to write in some logic error if we ever want to add code here.

So, if you must omit the braces, we should write:

if (lockers[i]) System.out.println("locker " + i + " is open.");

But I think it's better to just add the braces:

if (lockers[i]) {
    System.out.println("locker " + i + " is open.");
}

But alternatively, here might be a place to use our ternary if we want to print the status of all of the lockers. Eliminate the if:

System.out.println("locker " + i + " is " + (lockers[i] ? "open" : "closed"));
\$\endgroup\$
7
\$\begingroup\$

You've used a 101-element array instead of a 100-element array, which is fine. However, in that case, you should avoid mentioning lockers[0] altogether. The printout loop should be:

for (int i = 1; i < lockers.length; i++) {
    if (lockers[i]) {
        System.out.println("Locker " + i + " is open.");
    }
}

It would be better to avoid hard-coding 100 as a loop limit, and compare against the array length instead.

I suggest renaming the lockers to lockerIsOpen, so that the true=open, false=closed convention is self-documented.

\$\endgroup\$
5
\$\begingroup\$

After the "game" completes, the open (true) lockers will be exactly those lockers whose number is a perfect square. (Proof.) Therefore, you can eliminate both the the O(N2) loop nest and the O(N) workspace:

public class Main {
    public static void main(String[] args) {
        for (int i = 1; i*i <= 100; i++)
            System.out.println("Locker " + (i*i) + " is open.");
    }
}

If I were going to hand this in as an answer to a homework problem, I would include the proof in a large comment above the code, to make clear why this is an answer to the question posed.

If I were going to assign this as a homework problem I think I would make it a two-part question: first, do it the obvious way with an array and two loops; second, there's a way to do it in linear time and constant space, find out how and prove it's reliable.

Note 1: Hardwiring the upper limit is a bad code smell. Ideally, one would accept the upper limit as a command-line argument. I don't actually speak Java and therefore I don't know how to do that (specifically, I don't know what exactly will be in args[] or how to convert a string to a number and check for overflow).

Note 2: Formally unnecessary parentheses around the i*i on the System.out.println line are there because string-concatenation + is not mathematical addition, so readers might hesitate to assume that the precedence of * is higher.

Note 3: Curly braces were omitted around the one-line loop very much on purpose.

\$\endgroup\$
  • 1
    \$\begingroup\$ This is probably missing the point of the programming exercise though. And after reading the first paragraph of the question again, specifically what the OP didn't ask for. ;) \$\endgroup\$ – Reinstate Monica Apr 12 '15 at 20:11
  • \$\begingroup\$ the optimal program for this problem looks like this: Well... It depends on what you mean with optimal. From memory usage and executable size that is probably true. For optimal CPU usage something like print("Locker 1 is open.\nLocker 4 is open.\nLocker 9 is open...") probably turns out to be better ;-). \$\endgroup\$ – yankee Apr 12 '15 at 20:27
  • \$\begingroup\$ @ABoschman I guess that might be what the OP meant by "printing out the square roots"? It doesn't jump out at me. \$\endgroup\$ – zwol Apr 13 '15 at 14:03
  • \$\begingroup\$ @yankee If I knew how (I don't actually know Java) I would have written this program to read the upper limit as a command line argument. Maybe that should be a third note, come to think of it. \$\endgroup\$ – zwol Apr 13 '15 at 14:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.