What is the best solution for the 'Students and Lockers' problem?

Question

I thought that it would be fun to present some classic CS problems and let people show their algorithm optimization skills. The hope is that we get to see some clever techniques to solve abstract problems that we may be able to implement in practice.

Ideally solutions would be presented in pseudo code with a big O classification. Proof of that classification is gravy. On to the problem:

There are N closed lockers and N students present. The first student opens each locker. The second student opens or closes every second locker. This continues where the nth student opens and closes every nth locker. After N students what lockers are open? How many lockers are open?

Answer 1

Students will only flip the state of those lockers that their number is a divisor of (student 2 flips the even lockers, student 3 flips the lockers divisible by 3, so on and so forth...). So, the only lockers that will remain open after N rounds are those that have an odd number of divisors (because they start closed, an odd number of flips will leave it open). The only numbers that have an odd number of divisors are perfect squares, so all of the perfect-square-numbered lockers will be left open. So after N rounds, the number of lockers left open will be the square root (floored) of N.

This solution would be O(sqrt(N)) to know exactly which lockers are open, but O(1) if you only need to know how many lockers are open.

Answer 2

In O(log N) based on the interval of open lockers following the series 1+2k:

delta=1

for(index=1;index < N;index+=delta) {
   print open locker = index;
   delta+=2;
   opencount++;
};

Answer 3

I thought I would see how quickly I could come up with a solution in Perl.

use strict;
use warnings;
use 5.010;

sub lockers{
  my($number_of_lockers) = @_;

  my $largest_sqrt = sqrt $number_of_lockers;

  my @list;

  for( my $index = 1; $index <= $largest_sqrt; ++$index ){
    push @list, $index**2;
  }

  return @list;
}

say for lockers 100;

1
4
9
16
25
36
49
64
81
100

Or, if you don't want to calculate the Square root, of the number of lockers.

use strict;
use warnings;
use 5.010;

sub lockers{
  my($number_of_lockers) = @_;

  my @list;

  for(
    my($index,$sqr) = (1,1);
    $sqr <= $number_of_lockers;
    $sqr = (++$index)**2
  ){
    push @list, $sqr;
  }

  return @list;
}

say for lockers 100;

Answer 4

Just had this as a hw assignment.

for(int i = 0; i < SIZE / 2; i++){
   for(int k = i; k < SIZE; k = k+i+1){
      if(lockers[k] == false)
        lockers[k] = true;
      else
        lockers[k] = false;
   }
}