troublefish troublefish - 29 days ago 22
C Question

Student Locker puzzle

/* There are 100 students and 100 lockers. Student 1 opens all, student 2 closes every second one, student 3 changes every third
locker(closes if open, opens if close), Student 4 changes every forth locker and so on for all 100 students.
Which locker will be left open? */

Here is my code thus far:

#include <stdio.h>

int main(void)
{
int locker[100], i, closed = 0, opened = 0;

for(i=0; i<100; i++) locker[i] = 1;//0 means closed locker, 1 means open locker
for(i=1; i<101; i++) if(i % 2 == 0) locker[i-1] = 0; // every second locker is closed by second student...(2,4,6,7)
for(i=3; i<101; i++){ // i means student no. i
if(locker[i-1] == 0) locker[i-1] = 1;
if(locker[i-1] == 1) locker[i-1] = 0;


if I substitute "if(locker[i-1] == 1)" with "else" why the program doesn't work? Correct result is opened 1 closed 99. If I use 'else' result becomes opened 50 and closed 50

}
for(i=0; i<100; i++){
if(locker[i] == 0) closed = closed + 1;
else opened = opened + 1;
}
printf("opened locker %d\nclosed locker %d", opened, closed);
return 0;


}

This is my first post in stack overflow. Correct me if I've done anything wrong.

Answer

I'll give you a few hints to help you out.

  • The answer is that 10 lockers remain open, 90 are closed.
  • For this particular problem, it's easier to write the code if you avoid zero-based indexing. So declare the array as int locker[101]; and then use indexes 1 thru 100 to represent the 100 lockers.
  • The Nth student is supposed to change every Nth locker. So you need two nested for loops. The outer loop keeps track of n, and the inner loop flips lockers.
  • The inner loop that only affects every Nth locker should look like this

    for ( i = n; i <= 100; i += n ) // every Nth locker
        locker[i] = 1 - locker[i];  // flip the locker
    

    Note that instead of the normal i=0 and i++, we have i=n and i+=n. So, for example, if n is 3, then the values of i are 3,6,9,...