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.

5 Answers

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,...

Though I have not checked entire code and the logic of your question is not very clear to me, these lines seem to be problematic in your code:

if(locker[i-1] == 0) locker[i-1] = 1; if(locker[i-1] == 1) locker[i-1] = 0; 

What you're doing here is if a value is 0, then you are setting it to 1, then you are checking again, if it is 1, you are setting it to 0. So, so in this case all values will be set to 0 after running through both these statements.

Instead you should be doing

if(locker[i-1] == 0) locker[i-1] = 1; else locker[i-1] = 0; 

Note that your loop is wrong because you are looping over every locker for the third student and not looping over the remainder. You should for each student (n) change every nth locker to the reverse.

Also when you have the two ifs in a row. If the first if opens a locker, the second if sees it open and closes it (which is wrong). The else is required to actually change it.

Another point is that you can use exclusive or instead of the if locker[i] ^= 1

#include <stdio.h> int main(void) { int locker[100], i, k, closed = 0, opened = 0; for(i=0; i<100; i++) { if (i%2 == 0) locker[i] = 1; // odd lockers (base 1) stay open else locker[i] = 0; // even lockers (base 1) are closed //0 means closed locker, 1 means open locker for(i=3; i<101; i++){ // i means student no. i for (k=i; k<101); k+=i) { // change every ith locker // if (locker[k-1] == 0) locker[k-1]=1 // else locker[i-1] = 0; // use exclusive or instead of if locker[i-1] ^= 1; } } } // Now check the number open or closed 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; 

}

solution without using an array.

#include <iostream> using namespace std; int main() { int studentTotal , lockerTotal, visit, totalOpened = 0, totalClosed = 0; cout << "Enter number of students" << endl; cin >> studentTotal; lockerTotal = studentTotal; for (int locker = 1; locker <= lockerTotal; locker++ ){ // locker loop cout << "\n\n\nLocker no." << locker << endl; cout << " is visited by student(s) "; visit = 0; for (int student = 1 ; student <= studentTotal; student++) { // student loop if( locker % student == 0) { cout << student << ", "; visit++;} }//end of locker loop cout << "\nTotal number of visits: " << visit; if (visit % 2 == 0){ cout << " the locker will stay closed."; totalClosed++;} else { cout << " the locker will be opened."; totalOpened++;} } //end of student loop if (lockerTotal == totalOpened + totalClosed) { cout << "\n\n\nOf total lockers (" << lockerTotal << "), " << totalOpened << " will be left open." << "(" << totalClosed << ") " << "will be closed." << endl; }else cout << "Error!!"; return 0; } 

LOCKERS is the new FIZZBUZZ.

Here's a version which uses Booleans.

/* locker problem.c */ #include <stdio.h> #include <stdbool.h> int main (void) { bool locker[101]; // locker open = true, closed = false // student 1 opens all lockers for (int i = 1; i <= 100; ++i) { locker[i] = true; } // subsequent students toggle (flip) subsequent lockers for (int i = 2; i <= 100; ++i) { for (int j = i; j <= 100; j += i) { locker[j] = ! locker[j]; } } // display results printf("\nopen lockers:"); for (int i = 1; i <= 100; ++i) { if (locker[i]) { printf(" %d", i); } } putchar('\n'); return 0; } 

At the conclusion of the process the open lockers are the ones with a number which is a perfect square -- a perfect square has an odd number of divisors.