Finding the Nth open door

As a follow up to my previous post about the 100 Door Puzzle, I realised there is a variation of the question where there is an even faster answer.

If the question is: which door is the n^th open door (for example tell me where the 5th open door is) then the answer is: n² or as per the example 5²=25 (the 25th door along is the 5th open door)

  private static int NextOpenDoorIsAt(int nthOpenDoor)
  {
   return (int)Math.Pow(nthOpenDoor, 2d);
  }

So in the case where you only need to find the n^th door that is open this is a faster method. This of course could be applied to my previous post to give an O(√N) solution for the whole series - the faster being down to the speed of summation vs. product.

Toggle door puzzle, fast solution

I was recently asked the following question:

You have 100 doors in a row that are all initially closed. you make 100 passes by the doors starting with the first door every time. the first time through you visit every door and toggle the door (if the door is closed, you open it, if its open, you close it). the second time you only visit every 2nd door (door #2, #4, #6). the third time, every 3rd door (door #3, #6, #9), etc, until you only visit the 100th door.

question: what state are the doors in after the last pass? which are open which are closed?

If the questions is expressed as is door N open, the answer is

bool doorOpen = (Math.Sqrt(doorNumber) % 1) == 0;

However, as part of going through the puzzle I noticed that there seemed to be a sequence in the offset of the open doors (1, 4, 9), which looked suspiciouly like odd number offsets: 1=1, 4=1+3, 9=4+5 i.e. the value of the offset of the next open door is the previous open door offset plus the next odd number.

Which when I applied it to larger doorsets worked as well. Looking at 50 doors, which doors are open (O) vs closed (c):
[OccOccccOccccccOccccccccOccccccccccOccccccccccccOc]

If you are given the problem of find all open doors in the set, then using the square root approach is O(n). So the square root approach would look like:

private static BitArray GenerateDoorTogleSeriesResult(int doors)
  {
   BitArray result = new BitArray(doors);

   for (int door = 1; door <= doors; door++)
    result[door - 1] = (Math.Sqrt(door) % 1) == 0;

   return result;
  }

whilst my approach looks like:

private static BitArray GenerateDoorTogleResult(int doors)
  {
   BitArray result = new BitArray(doors);

   int odd = 1;
   for (int door = odd; door <= doors; door += odd)
   {
     result[door - 1] = true;
     odd += 2; // next odd number
   }
   return result;
  }

The difference being that for 1,000 doors the square root apprach requires 1,000 square root calculation, whilst mine requires 31 summations. Or in big-oh O(√n).

The calling code looks like:

static void Main(string[] args)
  {
   const int DOORS = 10;
   BitArray suggestedAnswer = GenerateDoorTogleResult(DOORS);
   BitArray fastAnswer = GenerateDoorTogleSeriesResult(DOORS);

   Console.WriteLine("suggested:\n{0}", ShowDoors(suggestedAnswer));
   Console.WriteLine("fast\n{0}", ShowDoors(fastAnswer));
   Debug.Assert(ShowDoors(suggestedAnswer).CompareTo(ShowDoors(fastAnswer)) == 0);
  }

  private static string ShowDoors(BitArray doors)
  {
   StringBuilder sb = new StringBuilder(doors.Length+4);
   sb.Append("[");
   foreach (bool doorOpen in doors)
    sb.Append(doorOpen == true ? 'O' : 'c');
   sb.Append("]\n");

   return sb.ToString();
  }

I subsequently found the proof for this by Francesco Maurolico in 1575.

1575: "Arithmeticorum Libri Duo" by Francesco Maurolico is the first book
to prove a theorem by Mathematical Induction. The theorem was known 2000
years earlier by Pythagorus, but they proved it geometrically. The
theorem is that the sum of the first N odd numbers
1 + 3 + 5 + 7 + 9 + 11 + 13 +... + (2N-1) = N x N