Basics 0/97

Loops and simulation · 2 of 2

Simulation

Carry out a process step by step: keep its state, apply each step in the right order, move on a grid with direction arrays, and skip ahead when the steps repeat.

3,786 words · 17 min read

Part 1 of 9 Simulating a process

Carry out the steps the statement describes

Some statements describe a process in full: what there is at the start, and what happens in each step. They then ask how things stand at the end, or how many steps it takes for something to happen. When the number of steps is small enough, the direct method is the right one. We keep the current state in variables, apply the rule for one step, and repeat. A program that does this is a simulation.

Writing a simulation means reproducing the statement's rules exactly. Before writing one, check that it is fast enough by multiplying the number of steps by the work in one step.

You get a non-negative integer num. In one step, divide it by 2 if it is even, or subtract 1 if it is odd. Return how many steps it takes to reach 0.

Constraints

  • 0≤num≤1060 \le \text{num} \le 10^6

Sample 1 · Input

num = 14

Output

6

Sample 2 · Input

num = 8

Output

4

From 14 the values are 14, 7, 6, 3, 2, 1, 0, which is six steps. The state is the current number and the count of steps so far, and the loop applies one step at a time until the number is 0:

Sign up to run
def number_of_steps(num):
    steps = 0
    while num > 0:
        if num % 2 == 0:
            num //= 2
        else:
            num -= 1
        steps += 1
    return steps

print(number_of_steps(14))
print(number_of_steps(8))

Output: 6 and 4, the two samples.

A while loop fits because the statement says when the process ends, not how many steps it has. We should be sure that it does end. Every step makes the number smaller, by halving it or by subtracting 1, and a whole number that keeps getting smaller must reach 0.

We can also bound the number of steps. Subtracting 1 from an odd number leaves an even number, so two subtractions never come in a row: there is a halving between them. Every step makes the number smaller, and each halving divides it by 2, so after 19 halvings the number is at most 106/219≈1.910^6 / 2^{19} \approx 1.9. By then it is 1 or 0, so there are at most 19 halvings. With at most one subtraction before each halving and one more to take 1 to 0, that is at most 19+19+1=3919 + 19 + 1 = 39 steps. Trying every allowed input gives a maximum of 38, far inside any time limit.