Dropping Balls

You are given K balls and a building with N floors. You know that there is a floor X < N such that when you drop the ball it crashes to the ground of the building. Below X it does not crash, Above X it will. What is the minimum number of ball drops you need to determine the point of break.

Solution:

This is a classical G question and there is a simplified variant.  "There are 100 floors in a building. If you drop a glass ball from a floor down to the ground, it may or may not break. There's this threshold floor where dropping a ball from this floor or the above breaks the ball but dropping a ball from any floor below it won't. Now you are given only two glass balls to locate the threshold floor. How do you find it quickly?"

1st attempt: if you start from binary search then you are going in the wrong direction. K will be O(log N) but the key observation is that K is a constant here and there is the risk that you end your balls with not result. In the above example it's clear that you can consume 2 balls without getting a result with N=100.

2nd attempt: if you have K=1 there is nothing else you can make but a linear search starting from floor 1, and there is the implicit assumption that you can go back to the ground floor collect the surviving ball and redrop it. If you have K=2,  you can start from level 2: if it breaks, you can use the remaining one and go to level k-1 and conclude your test, if it does not break you still have two balls. The key intuition is that you can go up to the K level and if it breaks you can use the remaining one for K-1 attempts. So you can adopt the following approach for selecting the steps

K, K+(K-1), K+(K-1)+(K-2), K + (K-1) + (K-2) + (K-3) -> N = K + (K-1) + (K-2) + .. + 2 +1 = K (K+1)/2

2, 2+1, 2+1+

which gives you a way to get K given N. Now, you can generalize with more than 2 balls