Programming: 2 Crystal Balls

2 Crystal Balls

There are two identical crystal balls and one needs to find out which is the maximum floor in a 100 story building from where the balls can fall before they break. In the most efficient way, what will be the maximum number of drops required to find the right floor in any possible scenario?

This can be represented in a sorted array of 100 elements

[0, 0, 0, 0, 0, ..., 0, 1, 1, 1, 1, 1, 1, 1, ..., 1]
                        ^  where is this?

So each time you find a 1, it will break, and will only have 1 ball left. So you can only find the 1 twice (break 2 balls).

You can’t use the binary search since you can only find the 1 twice and

Using static jumps O(sqrt N)

As explaned in the search, the number of comparations is n/k + k-1. So the optimal number of jumps is k = sqrt(N). If the ball breaks, we can jump back and do a linear search. If the ball doesn’t break, we can jump to the next 10 floors. With N=100 the worst case is 10 + 9 = 19 drops.

using dynamic jumps O(sqrt N)

If we use dynamic jumps, we can start jumping k values and decrease a value each jump. The sum can be represented as a Gauss sum:

k + ... + 4 + 3 + 2 + 1 = k(k+1)/2

Since the jumps need to reach the last floor (N), k needs to be 14.

Code:

int crystalBalls(int arr[], int lenght) {
  int i;
  int jump = ceil(1/2.0 * (sqrt(8 * lenght + 1) + 1));

  printf("jump: %d\n", jump);

  for (i = jump; i < lenght; i += jump) {
    if (arr[i] == 1) {
      break;
    }
    jump--;
  }
  for (int j = (i - jump); j < i; j++ ) {
    if (arr[j] == 1) {
      return j;
    }
  }
  return -1;
}