Here I have a problem in understanding the optimal testing strategy.

In a scenario, You have been given two laptop batteries and a testing device. The testing device will make the battery connected to it (one battery can be connected at a time) deliver x mA, where x is an integer. The testing device is constructed in such a way that the battery will always explode if there’s any risk of explosion at that current.

Now we want a program that receives inputs. Input consists of multiple lines, one line per case (at most 200 test cases). Each line contains a single positive integer n between 1 and 4711 inclusive, giving the current at which the battery is known to explode. Input is terminated by a line containing 0, which should not produce any output.

And produce Output, where for each case, print one line containing the worst-case number of tests to perform when using an optimal testing strategy.

|  Sample Input   |  Sample Output   |
|--------- -------|------------------|
    1                0
    2                1
    10               4
    23               7

This was a programming contest question marked as an easy question. but I do not get the definition of the optimal testing strategy. What can be the boundaries? Generally what this question means?

  • 2
    $\begingroup$ I have a feeling that you haven't described the complete problem. As stated, it is not clear what is a testing strategy, so the question is unanswerable. $\endgroup$ Commented Jan 30, 2019 at 5:12
  • 2
    $\begingroup$ Please add a reference to the original source in the question. $\endgroup$
    – John L.
    Commented Jan 30, 2019 at 5:56

2 Answers 2


in my opinion, The designer of this question just wanted to make a famous algorithm problem a bit complicated but made it totally nonsense.

This is the famous two egg problem where

You are given two eggs and access to a 100-story building. Both eggs are identical. The aim is to find out the highest floor from which an egg will not break when dropped out of a window from that floor. If an egg is dropped and does not break, it is undamaged and can be dropped again. However, once an egg is broken, that’s it for that egg.

  • $\begingroup$ Not sure how you'd get to the answers above using the the equation from "The two egg problem"? Square root in this case should be 96.568, so for example not sure how that would allow you figure out that 9 is the optimal current for input 10 by performing only 4 checks? $\endgroup$ Commented May 18, 2020 at 13:06
  • $\begingroup$ @TodorKolev you start at 4, (4+ 3), (4 +3 +2), (4 +3 + 2+ 1) currents ? that is, 4, 7, 9, 10 in the worst case ? So the answer is 4 ? $\endgroup$ Commented May 31, 2020 at 8:40
  • $\begingroup$ Also, how do you select the right root to chose to as the starting floor ? I see that the link you have pointed to just uses the positive roots. However, when you have say 17, you have roots as 5.352349955359813, and -6.352349955359813. How do we deal with this ? The answer seems to be 6 in this case. $\endgroup$ Commented May 31, 2020 at 19:16

The question is badly posed, either because the person posing the question isn't very good at writing English, or because you copied or paraphrased it badly. As asked, we have no idea what "an optimal strategy" is or what it is supposed to be. The crux of the problem is in "giving the current at which the battery is known to explode" instead of "giving a current at which the battery is known to explode". And of course "will always explode if there’s any risk of explosion at that current" is more than problematic.

In the "two egg problem" the optimal strategy is obviously one that minimises the number of stairs that I need to climb, which is likely to invalidate most answers that you find.

In case of the battery, I'd investigate how long it takes until the battery explodes, how much money the tester is paid per hour, and what the cost of an exploding battery is, and determine the optimum strategy from this information.


Not the answer you're looking for? Browse other questions tagged or ask your own question.