CODEWITHSUNDEEP
javaarraysloops
gzaw
gzaw

Reputation: 135

Java Array and Loop

There's a lightbulb problem in which 100 people perform a task. Someone implemented code to solve this problem:

 boolean[] bulbs = new boolean[100];

 for(int i = 1; i < bulbs.length; i++){//loops through people

My question is; isn't this piece of code only looping through 99 people?

If you're interested in the original problem, it goes like this:

There are 100 light bulbs lined up in a row in a long room. Each bulb has its own switch and is currently switched off. The room has an entry door and an exit door. There are 100 people lined up outside the entry door. Each bulb is numbered consecutively from 1 to 100. So is each person.

Person No. 1 enters the room, switches on every bulb, and exits. Person No. 2 enters and flips the switch on every second bulb (turning off bulbs 2, 4, 6...). Person No. 3 enters and flips the switch on every third bulb (changing the state on bulbs 3, 6, 9...). This continues until all 100 people have passed through the room.

What is the final state of bulb No. 64? And how many of the light bulbs are illuminated after the 100th person has passed through the room?

Also if you're interested, the entirety of the code is:

    boolean[] bulbs = new boolean[100];

for(int i = 1; i < bulbs.length; i++){//loops through people
    for(int j = 0; j<bulbs.length;j+=i){//loops through bulbs
        bulbs[j] = !bulbs[j];
    }
}

//print out all the "on" bulbs
for(int i = 1; i<bulbs.length;i++){
    if(bulbs[i]){
        System.out.println(i + ": "+ bulbs[i]);
    }
}

Upvotes: 0

Views: 2197

Answers (3)

Jef Vrijhoeven
Jef Vrijhoeven

Reputation: 102

Your problem arises from the fact that your persons and bulbs are numbered from 1 upward, but your array is indexed from 0 upward.

1 simple solution could be that you create an array of 101 indexes, and don't use the first index (set it to false, so that the bulb is never activated, and will not influence your result of number of active bulbs at the end).

Or, you can keep your array of 100 indexes, and translate between index and person/bulb number everytime you address a person or a bulb. The code would become:

for (int i = 0; i < bulbs.length; i++)
    for (int j = i; j < bulbs.length; j = j + i + 1)
        bulbs[j] = !bulbs[j];

This way: - all 100 persons enter the room (first loop) - the loop over the bulbs goes in steps of the person's number (e.g. person nr 1 has index O, so "j = j + i + 1" increases j by 1 in every step, person 2 has index 1, so "j = j + i + 1" increases j by 2 in every step, and so on)

Note: the loop over the bulbs must start from "i" and not from "0", otherwise each person will switch the 1st bulb, and then each n'th bulb (e.g. person 2 would switch the indexes 0, 2, 4, ... which are bulbs nr 1, 3, 5, etc due to the difference between people/bulb numbering and the indexes) With my code, person 1 (index 0) will switch all bulbs person 2 (index 1) will switch indexes 1, 3, 5, .. which are the bulbs 2, 4, 6, ..

Upvotes: 2

CounterFlame
CounterFlame

Reputation: 1632

No, i should not be initialized as 0, as that would mean that on the next rule:

for (int j=0; j<bulbs.length;j+=i)

j would remain on 0 indefinitely.

I do think that:

 for(int i = 1; i < bulbs.length; i++)

should become:

 for(int i = 1; i <= bulbs.length; i++)

so that it actually loops from 1 to 100, instead of 1-99.

As for the final part: What is the final state of bulb No. 64? And how many of the light bulbs are illuminated after the 100th person has passed through the room?

System.out.println("State bulb 64: " + bulbs[63]); // if we assume bulbs[0] is considered as bulb number 1
int count = 0; 
for (int i=0; i<bulbs.length; i++) {
    if (bulbs[i]) 
        count++;
}
System.out.println("# lightbulbs on:" + count);

Upvotes: 1

jotadepicas
jotadepicas

Reputation: 2493

Yes. i should be initialized to zero, not one, to loop through the entire array.

Upvotes: 4

Related Questions