Analysing programs: from the output back to the input

In an ordinary task you get the program and the input and find the output. DİM often asks the opposite: «If 77 is printed, what is the smallest value of m?», «How many natural numbers can be entered so that 9 is printed each time?». Each of the four 2025–2026 papers had at least one such «reverse» task, and three of them were coded tasks where you write the answer yourself. In this lesson you first learn the trace table and then a four-step method for reasoning from the output back to the input. The rules of loops are in «Loops: for, while, step, break, continue and nested loops» and «Working with numbers: digits, divisors and primes».

The trace table: what does the program print?

In a while loop the condition is checked before the body: as soon as it is false, the loop ends and the program moves to the line after the loop. So after the loop the variables keep the values of the last iteration.

1. 1
   Set up the columns

   every variable that changes in the loop plus a «yes/no» column for the condition.

2. 2
   Write the starting values

   the assignments before the loop go into the first row.

3. 3
   Check the condition

   «yes» — run the body line by line from top to bottom and start a new row; «no» — stop.

4. 4
   Look at print

   the printed expression may not be the variable itself (n + k, m * 10 + k); print(a, b) prints two values separated by a space.

s = 0
k = 1
while s < 40:
    if k % 2 == 0:
        s = s + k * k
    else:
        s = s + k
    k = k + 1
print(k, s)

7 65

How many times did the loop run? From the output to the number of iterations

The first step of a reverse task is always the same. If the printed variable changes by the same rule at every iteration (the same number is added, or it is multiplied by the same number), its final value gives the number of iterations k. The input is not needed yet at this step.

From the condition to inequalities: the smallest and the largest input

If the loop ran exactly k times, two facts hold: after iteration k − 1 the condition was still true (otherwise iteration k would not have started), and after iteration k it became false (the loop stopped). These two sentences give two inequalities for the input.

1. 1
   Find k

   the number of iterations from the printed value.

2. 2
   Express the variable through the input

   for example, after k steps s = 25 + k · m.

3. 3
   Write two inequalities

   after k steps the condition is false, after k − 1 steps it is true.

4. 4
   Pick the whole-number solutions

   the smallest or the largest natural value; the number of all suitable inputs is R − L + 1.

m = int(input())
n = 2
s = 25
while s <= 900:
    s = s + m
    n = n + 5
print(n)

a = int(input())
n = 1
while a > 5:
    a = a // 3
    n = n * 2
print(n)

How many inputs give the same output?

Here we find both the smallest input (L) and the largest (R). If all whole numbers between them fit, the answer is R − L + 1 (both ends count). If the amount added in the body changes (s = s + k * 4), the total over k steps is the sum of an arithmetic sequence.

s = int(input())
k = 1
while s < 300:
    s = s + k * 4
    k = k + 1
print(k)

for m in range(1, 101):
    n = 2
    s = 25
    while s <= 900:
        s = s + m
        n = n + 5
    if n == 77:
        print(m)

59
60
61
62

Digits, formulas and functions

If a program takes a number apart into digits, the output tells you two things: how many digits there are and one fact about them (their sum, product…). To build the largest number, put the big digits on the left; in the smallest number the first digit must be at least 1 and the rest of the sum goes to the right as 9s.

y = int(input())
m = 0
n = 0
while y > 0:
    m = m + 3
    n = n + y % 10
    y = y // 10
print(m, n)

For «Which expression does the program compute?» write the first 2–3 iterations into a trace table and spot the pattern of the terms. Then test the options with n = 1 and n = 2.

n = int(input())
s = 0
p = 1
for i in range(1, n + 1):
    p = p * 2
    s = s + i / p
print(s)

The loop condition may contain a function (see «Functions: def, parameters and return»). First write down which expression the function returns, then solve the condition as an ordinary inequality.

def f(x):
    return x * x

def g(x):
    return 5 * x + 6

k = abs(int(input()))
i = 1
while f(i) <= g(k):
    i = i + 1
print(i)

lo = 0
hi = 0
c = 0
for x in range(1, 401):
    s = x
    k = 1
    # the loop of Example 6 here

    # if k == 9, update lo, hi and c

print(lo, hi, c)

156 187 32

best = 0
for x in range(1000, 10000):
    y = x
    m = 0
    n = 0
    # the loop of Example 7 here

    # remember x if the program would print 12 21

print(best)

9930