Skip to content

✢ Guess-and-Check

Learning Objectives

At the end of this sub-unit, students should

  • know how to apply guess-and-check to problem solving.

Preliminary

In school, guess-and-check is probably the first problem solving technique you have learnt. This is quite a simple technique because the only thing we need to know is how to check if a particular value is the correct answer or not. Checking is often easier than solving via other means. Unfortunately, it may not be applicable for all problems.

Consider the problem of finding a solution to a particular cubic equation such as \(x^3 + 6x^2 + 11x + 6\). Guessing that it can be factorized into \((x + 1)(x^2 + 5x + 6)\) is probably simpler than knowing that the solution can be computed using the formula below first published by Girolamo Cardano in 1545.

\[ \begin{align} x_1 & = S + T - \frac b {3 a} \\ x_2 & = - \frac {S + T} 2 - \frac b {3 a} + \frac {i \sqrt 3} 2 \left({S - T}\right) \\ x_3 & = - \frac {S + T} 2 - \frac b {3 a} - \frac {i \sqrt 3} 2 \left({S - T}\right), \\ \end{align} \]

where

\[ \begin{align} S & = \sqrt[3]{R + \sqrt{Q^3 + R^2}} \\ T & = \sqrt[3]{R - \sqrt{Q^3 + R^2}} \\ Q & = \frac{3ac - b^2}{9a^2} \\ R & = \frac{9abc - 27a^2d - 2b^3}{54a^3} \end{align} \]

for cubic equation of the form \(ax^3 + bx^2 + cx + d\).

Even writing it is tedious, imagine solving problems with it. On the other hand, once we have guessed the factorization, the remaining term \(x^2 + 5x + 6\) can be solved with the simpler quadratic formula. So we want to use guess-and-check when it can help us solves problem. The steps for guess-and-check is shown below.

Steps

  1. Start with an initial guess \(n\).
  2. Check if \(n\) is the correct answer.
    • If \(n\) is the correct answer, go to Step 3.
    • Otherwise, try the next guess for \(n\) then repeat Step 2 with the next guess.
  3. The answer is \(n\).

Guess-and-Check

Notice that there is a certain circularity in the flowchart. This implies that we need a loop to use guess-and-check.

Simplification

Guess-and-check is closely related to another general form of problem solving for programming problem called brute-force. In brute-force method, we simply enumerate all possible potential solution, kind of like how we try to enumerate all possible guess \(n\). Given the generality of it, we will first simplify our guess-and-check with the following simplification that we will relax one by one.

  1. There is only one unknown.
  2. There is an answer.
  3. We know the range where the answer can be found.
  4. The answer will be non-negative whole number.

We will remind you of the simplification made at the beginning of each section.

Simple Guess-and-Check

Simplification

  1. There is only one unknown.
  2. There is an answer.
  3. We know the range where the answer can be found.
  4. The answer will be non-negative whole number.

Birds and Cats

Problem Description

There is a total of animals number of birds and cats in the park. There are also legs number of legs. How many birds are there in the park?

Task

Write the function birds_and_cats(animals, legs) that accepts the number of animals and the number of legs. The function returns the number of birds in the parks.

Assumptions

  • animals and legs are positive integers (i.e., animals > 0 and legs > 0).
  • There is a non-negative number of birds as a solution.

If you know your algebra, this can be solved by letting animals be \(x\) and legs be \(y\) and solve for \(n\) in \(2n + 4(x - n) = y\). With a little bit of rearrangement, we can find that the solution is \(n = \frac{4x - y}{2}\).

The advantage of guess-and-check is that we do not have to know algebra to solve this. We can simply let the computer try out all possible number of birds. After all, computer will never get bored, we can give it as tedious a computation as we want without trying to be smart. We will also show the expected problem solving steps in details.

Understanding the Problem

Often, problem description is written by assuming a certain basic knowledge. If basic mathematical knowledge is needed, it is usually high school mathematics. Otherwise, it should be based on common sense and common knowledge.

In this birds and cats problem, there is no information on the number of legs of birds and cats. But based on common sense, we can deduce the following.

  • Birds have 2 legs.
  • Cats have 4 legs.

We will not deal with oddly numbered legs like the possibility of a cat with only three legs or counting the tail as a leg. So equipped with this information, we can create our own test cases. But remember, we do not have to know the exact relationship yet because there is another way to obtain test cases: working backwards.

By working backwards, instead of starting with some value of animals and legs, we simply start with some number of birds and cats. We can produce the following table below. Note that the table is intended to be read from right to left instead of left to right. That is, we fill in the rightmost column and compute to the left.

animals legs #legs in cats #legs in bids #cats #birds
\(3 + 2 = 2\) \(12 + 4 = 16\) \(4 \times 3 = 12\) \(2 \times 2 = 4\) \(3\) \(2\)
\(3 + 4 = 7\) \(12 + 8 = 20\) \(4 \times 3 = 12\) \(2 \times 4 = 8\) \(3\) \(4\)
\(4 + 2 = 6\) \(16 + 4 = 20\) \(4 \times 4 = 16\) \(2 \times 2 = 4\) \(4\) \(2\)

Try to come up with a few other test cases on your own to show that you understand the problem.

By working backwards, a few things become clearer. For instance, the relationship between the number of cats (#cats), the number of birds (#birds), and animals. This is one of the main advantages of creating our own test cases. We may shed light to some previously hidden relationships between the values.

Design Your Solution

Assuming that we know that this problem can be solved with guess-and-check, we can use the flowchart for guess-and-check as the basis of our design. We will show the flowchart horizontally below. Currently, there is no additional information, but we will furnish the flowchart with more details later.

GAC01

What we want to show is another trick when designing a solution: try specific values. Once you have gained more proficiency in problem solving, this step can be skipped. But for now, we will illustrate this with a specific value for animals and legs to guide our solution. We will choose the second row above.

  • animals = 7
  • legs = 20

Forget for a moment that the answer should be 4. How can we solve this with guess-and-check? The typical step can be illustrated by a table. But a table does not really do justice to the actual step as it is a static information. Instead, we will slowly build up the table row by row with each attempt.

Smart Way

The kind of guess-and-check that is typically taught is a "smart" version that may not be suitable for computer to solve. However, it is still a useful illustration. We start with a potentially good guess. It is always good to start in the middle, so we do that. We let the number of birds be 3. From here, we can compute the number of cats up to the number of legs.

#birds #cats #legs in birds #legs in cats legs
\(3\) \(7 - 3 = 4\) \(3 \times 2 = 6\) \(4 \times 4 = 16\) \(6 + 16 = 22\)

Now here comes another smart thinking.

  • Since 22 is greater than the required number of legs which is 20, we need to reduce the number of legs.
  • Since cats have more legs than birds, to reduce the total number of legs, we need to reduce the number of cats.
  • Since the total number of animals is the same, by decreasing the number of legs, we need to increase the number of birds.

So let's try what happen if we have 5 birds.

#birds #cats #legs in birds #legs in cats legs
\(5\) \(7 - 5 = 2\) \(5 \times 2 = 10\) \(2 \times 4 = 8\) \(10 + 8 = 18\)

Now we have too few legs. We need to increase the number of legs. Following the same reasoning as above, we need to decrease the number of birds. But we cannot choose 3 as we know that gives too many legs. So we choose 4 and we check.

#birds #cats #legs in birds #legs in cats legs
\(4\) \(7 - 4 = 3\) \(4 \times 2 = 8\) \(3 \times 4 = 12\) \(8 + 12 = 20\)

And so we arrive at the answer using 3 iterations including the last iteration that produces the answer. The full steps is illustrated below.

#birds #cats #legs in birds #legs in cats legs
\(3\) ↑ \(7 - 3 = 4\) \(3 \times 2 = 6\) \(4 \times 4 = 16\) \(6 + 16 = 22\)
\(5\) ↓ \(7 - 5 = 2\) \(5 \times 2 = 10\) \(2 \times 4 = 8\) \(10 + 8 = 18\)
\(4\) \(7 - 4 = 3\) \(4 \times 2 = 8\) \(3 \times 4 = 12\) \(8 + 12 = 20\)

Simple Way

Unfortunately, translating this smart way to code is harder than it looks. Our computer is not as smart as us. It requires a very precise and simple instructions. Can we simplify the steps so that even a computer can understand this? If we can do that, does not matter how long it takes, assuming that there is an answer, the computer will find the answer.

Here is an idea for simple guess-and-check.

Simple Guess-and-Check

Try all possible values.

But even with that simple motto, there is a lot to unpack. We can make this more specific by answering the following questions. Try answering the questions below on your own first before checking the answer. Your answer may be different and that is fine. We will look at the analysis later. For now, we will still be using the fixed number as above.

  1. What is the smallest value to check?
  2. What is the next value to check? Can you generalize this as an expression?
  3. What is the largest value to check?
  4. How do we check if a value is the correct answer?
  1. We can start from 1.
  2. We can simply check the next larger integer (i.e., guess = guess + 1).
  3. We can stop at 6.
  4. When the number of legs is exactly 20.

Using this idea, we can construct the table showing our works starting from the smallest until we find the answer.

#birds #cats #legs in birds #legs in cats legs
\(1\) ↑ \(7 - 1 = 6\) \(1 \times 2 = 2\) \(6 \times 4 = 24\) \(2 + 24 = 26\)
\(2\) ↑ \(7 - 2 = 5\) \(2 \times 2 = 4\) \(5 \times 4 = 20\) \(4 + 20 = 24\)
\(3\) ↑ \(7 - 3 = 4\) \(3 \times 2 = 6\) \(4 \times 4 = 16\) \(6 + 16 = 22\)
\(4\) \(7 - 4 = 3\) \(4 \times 2 = 8\) \(3 \times 4 = 12\) \(8 + 12 = 20\)

Using this simple way, we may need to do more iterations especially if the number of birds is larger. Even in the example, we need one more iteration than the smart way. Of course we may be lucky and the first iteration is the answer, but on average, we would not be as lucky. So that is the illustration of the simple guess-and-check.

Generalizing

All our works so far uses a fixed value. The next step in the design is to generalize it to the arbitrary value that animals and legs can take. We can do that by replacing \(7\) with animals and derive the value for the number of legs as a formula involving animals. This is captured by the table below. We will illustrate the values of birds from 1 to animals - 1 which is our assumed largest possible value. For simplicity, we will use \(x\) for animals and \(y\) for legs.

#birds #cats #legs in birds #legs in cats legs
\(1\) \(x - 1\) \(1 \times 2 = 2\) \((x - 1) \times 4 = 4(x - 1)\) \(2 + 4(x - 1)\)
\(\vdots\)
\(n\) \(x - n\) \(n \times 2 = 2n\) \((x - n) \times 4 = 4(x - n)\) \(2n + 4(x - n)\)
\(\vdots\)
\(x - 1\) \(1\) \((x - 1) \times 2 = 2(x - 1)\) \(1 \times 4 = 4\) \(2(x - 1) + 4\)

What we are interested in is the middle row. The expression \(2n + 4(x - n)\) is the total number of legs. We have the correct number of legs if this expression is equal to \(y\) (i.e., \(2n + 4(x - n) = y\)). So all of these hard work is only to find the single expression:

2 * guess + (4 * (animals - guess)) == legs

But at least we have completed our design. So it is time to furnish the flowchart with information from our design.

GAC02

Write Your Program

Before writing the program, we need to answer the specifics of the flowcharts. First, we have a diamond on our flowchart. Should this be a while-loop or an if-statement? We know that the condition is the complex expression from before. So if this is to be written as an if-statement, what will be the condition for the loop? Remember, we have a cycle in the flowchart, so a loop is necessary.

Considering that we have an initial guess of 1 and the largest guess of animals - 1, we can stop when guess == animals. In other words, we continue the iteration while guess < animals. A lazier condition will be simply True because we assume that there is an answer. But let us not be too lazy.

Once we have answered the questions, we can write the program as follows. Do not forget to write our additional test cases as well.

Birds and Cats

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def birds_and_cats(animals, legs):
  guess = 1
  while guess < animals:
    if 2 * guess + (4 * (animals - guess)) == legs:
      return guess
    guess = guess + 1

# Test Cases
print(birds_and_cats(5, 16) == 2)
print(birds_and_cats(7, 20) == 4)
print(birds_and_cats(6, 20) == 2)

1
2
3
True
True
True

Test Your Program

We simply run the code above and check the result. Assuming we have typed the code correctly, we should get the corresponding output as above. Great, so we can continue the next step.

Analyze Your Solution

In this step, we need to play the Devil's advocate. We need to question all our basic assumptions. Does it match with the given assumption stated in the problem description. Of course we also need to use common sense. Especially if the problem description may be incomplete either by design or by mistake. If it is by mistake, then it is best to ask for clarification. But the main task of questions our assumptions should still be done.

Often, we can find mistake by simply looking at the constant values used in the program. Since this constant values depends on the actual code written, there is no general technique in this step. Instead, we will illustrate this by questioning the constants in the code above. We construct a table of constants. Try to justify the constants below.

Value
4
2
1
Value Justification
4 This is the number of legs of a cat. We assume there is no cat with other number of legs based on common sense
2 This is the number of legs of a bird. We assume there is no bird with other number of legs based on common sense
1 Can there be 0 birds?

The last value is suspicious because based on the assumption in the problem description, we may have 0 number of birds.

There is a non-negative number of birds as a solution.

Non-negative is simply not a negative number. And \(x\) is negative if \(x < 0\). So non-negative implies \(x \geq 0\). In other words, it is possible to have 0 birds in the park!

This last value is also related to another part of the code, but it is harder to see. However, it should still be something we ask ourselves when looking at the code. With enough practice, you may be able to spot this on your code too. The reasoning goes like this.

  • If there can be 0 number of birds, there should also be 0 number of cats by common sense.
  • If there is 0 number of cats, the number of birds is equal to the number of animals.
  • That means, is should be possible that guess == animals.
  • Hence, the condition guess < animals in the while-loop is incorrect.

So now we have found two mistakes in the code by questioning our assumptions. That means, we have to go back to the drawing board and redesign our solution. To guide our design, we should also come up with additional test cases based on this new found understanding.

1
2
print(birds_and_cats(5, 20) == 0)  # no birds
print(birds_and_cats(5, 10) == 5)  # all birds

1
2
False
False

After adding these to our code, we can then rewrite the solution. Let us short-circuit the whole steps and produce the corrected solution below in the interest of time.

Birds and Cats

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def birds_and_cats(animals, legs):
  guess = 0
  while guess <= animals:
    if 2 * guess + (4 * (animals - guess)) == legs:
      return guess
    guess = guess + 1

# Test Cases
print(birds_and_cats(5, 16) == 2)
print(birds_and_cats(7, 20) == 4)
print(birds_and_cats(6, 20) == 2)

print(birds_and_cats(5, 20) == 0)  # no birds
print(birds_and_cats(5, 10) == 5)  # all birds

1
2
3
4
5
True
True
True
True
True

Simplified Design

Now that we understand guess-and-check a little bit better, we may be able to revamp the design step. Instead of always using the flowchart --which can be tedious to draw-- we can simply answer three questions instead. This assumes that the answer can always be found, so once we relaxed that condition, the table may change.

  • Mystery Function

    GAC01

  • Tabular

    Design Value
    Initial Guess \(n\)           
    Check \(n\)           
    Next Guess \(n\)           

Unbounded Guess-and-Check

Simplification

  1. There is only one unknown.
  2. There is an answer.
  3. We know the range where the answer can be found.
  4. The answer will be non-negative whole number.

Now we will relax the third simplification. Since this is only an illustration, the range can actually be found with a little bit of thinking. But there are indeed problems where we don't even know the range or even if there is even an answer. One such problem is the twin prime conjecture. If you can solve this, wealth, fame, and power will be yours1. So we use simpler example because it allows us to focus on the concept.

Unfactorial

Problem Description

Recap that the factorial of \(n\) written as \(n!\) is defined as follows: \(n! = 1 \times 2 \times \cdots \times (n - 1) \times n\). We have solved this problem before, but what we want is the inverse problem. If you are mathematician, feel free to call this the arcfactorial instead following the convention of arcsine and other inverse trigonometric function.

The problem is this. Given \(m\), find the smallest \(n\) such that the factorial of \(n\) is exactly \(m\). In other words, we want to find \(m\) that satisfies \(n! = m\).

Task

Write the function unfactorial(m) that accepts an integer m. The function returns the smallest n such that factorial(n) == m.

Assumptions

  • m is a positive integers (i.e., m > 0).
  • The function factorial(n) is already implemented correctly for n >= 0.
  • There is a non-negative integer solution.

An inverse problem actually has a nice way to generate test cases. If a function \(f\) is invertible with the inverse named \(f^{-1}\), then we can test for any number of \(n\) by using the following check: \(f^{-1}(f(n)) = n\). Factorial is not exactly invertible because both of the following produces 1: factorial(0) and factorial(1). But if we ensure that we do nto use m = 1, then we can write the following nice test.

unfactorial(factorial(n)) == n

At this point, we will short-circuit the entire problem solving step and simply write down some initial design for simple guess-and-check in tabular form. Then, by plugging in the design into the code, we get the code on the right.

  • Design

    Design Value
    Initial Guess \(n\) 0
    Check \(n\) factorial(n) == m
    Next Guess \(n\) n = n + 1

  • Code

    1
2
3
4
5
    def unfactorial(m):
  guess = 0
  while guess < m:
    if factorial(guess) == m:
      return guess

By analyzing our solution systematically, we found that the solution is incorrect for m = 2. This is because the answer is 2 but our guess will only cover 0 and 1. With a little bit more thinking, the solution is a simple modification to while guess <= m. But assume we do not know that.

Here, we will abuse the fact that there is a solution to just keep on checking for the next guess. This may result in an infinite loop but since our assumption includes the following.

There is a non-negative integer solution.

We can do an infinite loop trick. The idea is to exit prematurely using the return keyword when we have found the solution. Otherwise, keep on checking for the next guess. Note that we have to make sure we call this function with a value that has a solution. If our input m has no solution, our computer that can never feel bored will simply continue on indefinitely.

Unfactorial

1
2
3
4
5
6
def unfactorial(m):
  guess = 0
  while True:  # infinite loop!
    if factorial(guess) == m:
      return guess
    guess = guess + 1

Arbitrary Guess-and-Check

Simplification

  1. There is only one unknown.
  2. There is an answer.
  3. We know the range where the answer can be found.
  4. The answer will be non-negative whole number.

Now we want to learn how to stop. In particular, if there is no answer, it is futile to keep on guessing. Unfortunately, there is no easy way to do this as it will depend on the problem at hand. In the case of the twin prime conjecture, we do not even know if there is an infinite number of that.

Fortunately, for the two problems we solved above, we can check if there is no solution or not. We will simply add the following statement to the problem descriptions above.

If there is no solution, return -1.

Birds and Cats

The smart way to know when there is no more solution in the case of birds and cats problem is to figure out the following cases.

  1. There is no solution if the number of legs is an odd number.
  2. There is no solution if there are negative number of birds or cats.
    • If all birds, then the smallest number of legs is 2 * animals.
    • If all cats, then the largest number of legs is 4 * animals.
    • Any number outside of this range will not produce solution.

If we know the cases, we can check for these cases before even starting our main guess-and-check procedure. This gives us the following code.

Arbitrary Birds and Cats

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def birds_and_cats(animals, legs):
  if legs % 2 == 1:
    # odd number of legs
    return -1
  if legs < 2 * animals or legs > 4 * animals:
    # outside of range
    return -1
  guess = 0
  while guess <= animals:
    if 2 * guess + (4 * (animals - guess)) == legs:
      return guess
    guess = guess + 1

A simpler way is to just let the loop runs to completion. After all, we know exactly the range of potential solution. If we are outside of this range, then there is no solution. This gives us the simplified solution.

Arbitrary Birds and Cats

1
2
3
4
5
6
7
def birds_and_cats(animals, legs):
  guess = 0
  while guess <= animals:
    if 2 * guess + (4 * (animals - guess)) == legs:
      return guess
    guess = guess + 1
  return -1

Unfactorial

So if we know the range, then the arbitrary version of guess-and-check is trivial to do. If we do not know the range, then we need to figure out some patterns from the problem description. Consider the unfactorial problem, assuming we do not know the range, what can we do? We can first figure out if there is some check to indicate that we can no longer get a solution. We do this by finding some patterns from some small values of \(n\) and the corresponding \(n!\).

\(n\) 0 1 2 3 4 5 \(\cdots\)
\(n!\) 1 1 2 6 24 120 \(\cdots\)

The factorial function is non-decreasing2. Because it is a non-decreasing function, once we have the value of guess that is greater than m, we know that there is no longer any solution. Translating that into code.

  • There is no solution if the following condition is true: guess > m.
  • In other words, there is potentially some solution while guess <= m.

So now, we know our stopping condition and --more importantly-- we know the loop condition. Hence, instead of using infinite loop while True, we can use the loop condition above.

Arbitrary Unfactorial

1
2
3
4
5
6
7
def unfactorial(m):
  guess = 0
  while guess <= m:
    if factorial(guess) == m:
      return guess
    guess = guess + 1
  return -1

So this technique works because factorial is a non-decreasing function. Unfortunately, there is no generic solution and potentially, we may not even know if there is indeed always going to be a solution or not. So the best we can do is do quite a lot of thinking and figure out some properties from the problem description.

Small Generalization

Before we relax the last condition, we can do a little bit of generalization since we already learn about functions. Assuming we have one input parameter arg, the arbitrary guess-and-check can be rewritten as follows. You can try to generalize it for other number of parameters.

Arbitrary Guess-and-Check

1
2
3
4
5
6
7
def arbitrary(arg):
  guess = 0
  while has_solution(guess, arg):
    if check(guess, arg):
      return guess
    guess = next_guess(guess, arg)
  return no_solution(guess, arg)

Your task is to define the following functions which may simply return a constant.

  • has_solution(guess, arg)
  • check(guess, arg)
  • next_guess(guess, arg)
  • no_solution(guess, arg)

Floating Point

Simplification

  1. There is only one unknown.
  2. There is an answer.
  3. We know the range where the answer can be found.
  4. The answer will be non-negative whole number.

Agak-Agak Square Root

Problem Description

Given a positive \(m\), find an approximation of \(\sqrt{m}\) correct up to 2 decimal places.

Task

Write the function sqrt(m) that accepts an integer m. The function returns a floating point number \(n\) such that \(n\) differs from \(\sqrt{m}\) by at most \(0.01\).

Assumptions

  • m is a positive integers greater than 1 (i.e., m > 1).

Restrictions

  • You are not allowed to use the exponentiation operator ** or other related built-in functions (e.g., math.sqrt or others).

Small Increment

To arrive at the first potential solution, we need to know the limitation of our current guess-and-check. So far, our next guess is always guess = guess + 1. That is clearly a problem because our guess will always be an integer number. A direct extension of this is we simply use a smaller increment than 1. After all, we already generalize it into guess = next_guess(guess, arg). So why not just define it as follows.

1
2
def next_guess(guess, arg):
  return 0.01  # because 2 decimal places

Plugging this into the solution directly we get the following solution.

1
2
3
4
5
6
7
def sqrt(m):
  guess = 1  # no need to start from 0 because m > 1
  while (guess * guess) < m:
    if abs(guess * guess - m) < 0.01:
      return guess
    guess = guess + 0.01
  return guess

So this is good and it solves the problem. But unfortunately it may be too slow. It requires too many iterations. If the result is \(n\) we require \(100n\) iterations. If we increase the precision, we need more iterations.

Bisection

We can improve this using a technique called bisection. This is really beyond the scope but it is a nice technique. The high-level idea is to guess the range where the solution lies instead of the actual value. We will then make a better guess by restricting the range.

Bisection

  1. \(\sqrt{m}\) will be between \(\text{lower} = 1\) and \(\text{upper} = m\). This is because \(m > 1\).
  2. Consider the midpoint \(\text{mid} = \frac{\text{lower} + \text{upper}}{2}\).
    1. If \(\text{mid} < \sqrt{m}\) then answer is between \(\text{mid}\) and \(\text{upper}\). We set \(\text{lower} = \text{mid}\).
    2. If \(\text{mid} > \sqrt{m}\) then answer is between \(\text{lower}\) and \(\text{mid}\). We set \(\text{upper} = \text{mid}\).
  3. We stop when the answer is within two decimal places of \(\sqrt{m}\).

The code for bisection that solves the problem of approximating square root is shown below.

Bisection Square Root

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def sqrt(m):
  lower, upper=  1, m                  # Step 1
  mid = (lower + upper) / 2            # Step 2
  while abs(mid * mid - m) >= 0.01:    # Step 3
    if mid * mid < m:                  # Step 2a
      lower = mid
    else:                              # Step 2b
      upper = mid
    mid = (lower + upper) / 2          # Step 2: repeat for next iteration
  return mid

  1. Maybe even the One Piece! ↩

  2. It is not exactly increasing as \(0! = 1\) and \(1! = 1\) which clearly shows that it is not increasing. So the only thing we can say is that the value of \(n!\) will not decrease when \(n\) increases. ↩