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?
Trace tableDefinition
A table that shows the run of a program step by step: each column is a variable (plus the loop condition) and each row is one iteration of the loop.
Reverse taskDefinition
The program and its output are given, and the input is sought (the smallest, the largest or how many suitable values there are).
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.
Set up the columns
every variable that changes in the loop plus a «yes/no» column for the condition.
Write the starting values
the assignments before the loop go into the first row.
Check the condition
«yes» — run the body line by line from top to bottom and start a new row; «no» — stop.
Look at
printthe 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)Expected output
7 65
Example 1. The output of a program
Problem
Determine the output of the program above.
A) 6 65 B) 7 65 C) 7 29 D) 6 29 E) 8 65
Show solutionHide solution
Solution
1 | yes | 0 + 1 = 1
2 | yes | 1 + 2 · 2 = 5
3 | yes | 5 + 3 = 8
4 | yes | 8 + 4 · 4 = 24
5 | yes | 24 + 5 = 29
6 | yes (29 < 40) | 29 + 6 · 6 = 65
7 | no (65 < 40 is false) — the loop ends.
Printed: 7 65. Answer: B. Trap: after the loop k is already 7, not 6.
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.
Where
- n₀, s₀
- the values before the loop
- d
- the number added at each step (
n = n + d) - q
- the number multiplied by at each step (
s = s * q) - k
- the number of iterations
Adding gives an arithmetic sequence, multiplying gives a geometric one.
Example 2. The number of iterations
Problem
How many times did the loop run?
1) Before the loop n = 5, in the body n = n + 6, and 125 is printed after the loop.
2) s = 1, in the body s = s * 3, 243 is printed.
3) n = 2, in the body n = n * 4, 2048 is printed.
4) A counter k = 1, in the body k = k + 1, 8 is printed after the loop.
Show solutionHide solution
Solution
2) 3ᵏ = 243 = 3⁵ → k = 5.
3) 2 · 4ᵏ = 2048 → 4ᵏ = 1024 = 4⁵ → k = 5.
4) 1 + k = 8 → k = 7. If the counter starts at 1, the printed value is one more than the number of iterations.
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.
Where
- xₖ
- the value of the loop variable after k iterations, written through the input (for example s₀ + k · m)
The condition for the loop to run exactly k times.
Find k
the number of iterations from the printed value.
Express the variable through the input
for example, after k steps s = 25 + k · m.
Write two inequalities
after k steps the condition is false, after k − 1 steps it is true.
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)Example 3. The smallest input
Problem
Which smallest natural value of m must be entered so that the program prints 77? What is the largest suitable m?
A) 58 B) 59 C) 60 D) 62 E) 63
Show solutionHide solution
Solution
2) After k steps s = 25 + k · m.
3) After 15 steps the loop stopped: 25 + 15m > 900 → 15m > 875 → m > 58.3. After 14 steps the condition was still true: 25 + 14m ≤ 900 → m ≤ 62.5.
4) 59 ≤ m ≤ 62. The smallest is 59 (answer B), the largest 62; 4 inputs print 77.
Check: with m = 58, after 15 steps s = 895 ≤ 900 — the loop runs a 16th time and prints 82.
Where
- q
- the divisor (
a = a // q) - y
- the result of the integer division
A step back through integer division: the smallest x = q · y, the largest x = q · y + q − 1.
Example 4. Undoing integer division
Problem
For which x is 1) x // 3 = 5; 2) x // 10 = 42; 3) x // 2 = 7?
Show solutionHide solution
Solution
2) 420 ≤ x ≤ 429 — 10 numbers.
3) 14 ≤ x ≤ 15.
a = int(input())
n = 1
while a > 5:
a = a // 3
n = n * 2
print(n)Example 5. The largest and the smallest input (a coded task)
Problem
For the output 8, find 1) the largest natural value of a; 2) the smallest natural value; 3) how many such values there are.
Show solutionHide solution
Solution
1) The loop stopped: a₃ ≤ 5, the largest is a₃ = 5. At each step the largest x = 3y + 2: a₂ = 17, a₁ = 53, a = 161. The conditions hold: 161, 53, 17 > 5.
2) The 3rd iteration took place: a₂ > 5, i.e. a₂ ≥ 6 (6 // 3 = 2 ≤ 5 — the loop stops). The smallest x = 3y: a₁ = 18, a = 54.
3) 54 ≤ a ≤ 161: 161 − 54 + 1 = 108 values. If a coded task asks for «the difference of the largest and the smallest value», the answer is 161 − 54 = 107.
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.
Where
- L, R
- the smallest and the largest suitable input
- k(k + 1) / 2k(k + 1) / 2
- the sum of the first k natural numbers
The number of whole numbers in an interval and a sum with a growing step.
s = int(input())
k = 1
while s < 300:
s = s + k * 4
k = k + 1
print(k)Example 6. How many natural numbers give 9?
Problem
How many natural numbers can be entered so that 9 is printed each time?
A) 31 B) 32 C) 33 D) 144 E) 30
Show solutionHide solution
Solution
Added in 8 steps: 4 · (1 + 2 + … + 8) = 4 · 36 = 144; in 7 steps: 4 · 28 = 112.
After 8 steps the loop stopped: s + 144 ≥ 300 → s ≥ 156.
After 7 steps the condition was true: s + 112 < 300 → s < 188, i.e. s ≤ 187.
156 ≤ s ≤ 187: 187 − 156 + 1 = 32. Answer: B.
for m in range(1, 101):
n = 2
s = 25
while s <= 900:
s = s + m
n = n + 5
if n == 77:
print(m)Expected output
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)Example 7. Solving backwards by digits (a coded task)
Problem
The program printed 12 21. Find the largest and the smallest natural number that could have been entered for y.
Show solutionHide solution
Solution
Largest: the biggest possible digits from the left — 9, 9, then 21 − 18 = 3, and 0 at the end: 9930.
Smallest: the first digit is 1, and the remaining 20 is collected from the right: 9, 9, then 2 — 1299.
Check: 9 + 9 + 3 + 0 = 21, 1 + 2 + 9 + 9 = 21. If the difference is asked: 9930 − 1299 = 8631.
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)Example 8. Which expression does the loop compute?
Problem
Which expression does the program compute?
A) 1/2 + 1/4 + … + 1/2ⁿ
B) 1/2 + 2/4 + 3/8 + … + n/2ⁿ
C) 1/2 + 2/3 + … + n/(n + 1)
D) 2 + 4/2 + 8/3 + … + 2ⁿ/n
E) 1 + 1/2 + … + 1/n
Show solutionHide solution
Solution
i = 2: p = 4, s = 1/2 + 2/4
i = 3: p = 8, s = 1/2 + 2/4 + 3/8
At each step p becomes 2ⁱ and the numerator is i: the term is i/2ⁱ. Answer: B.
Check: for n = 3 the program prints
1.375, and 0.5 + 0.5 + 0.375 = 1.375.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)Example 9. Functions in the condition
Problem
1) −20 is typed on the keyboard. What is printed?
A) 10 B) 11 C) 12 D) 106 E) 9
2) For how many natural k is 11 printed?
Show solutionHide solution
Solution
2) To print 11 we need 10² ≤ g(k) < 11², i.e. 100 ≤ 5k + 6 ≤ 120 → 18.8 ≤ k ≤ 22.8 → k = 19, 20, 21, 22 — 4 numbers.
Exercise
Check Example 6: run its program for every s = 1, 2, …, 400 and print, on one line, the smallest s that gives 9, the largest such s and how many such values there are.
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)Expected output
156 187 32
Exercise
Check Example 7: among y from 1000 to 9999, find the largest number for which the program prints 12 21, and print it.
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)Expected output
9930
Remember
- The
whilecondition is checked before the body; after the loop the variables keep the values of the last iteration. - In a reverse task find k first: n = n₀ + k · d or s = s₀ · qᵏ.
- Exactly k iterations: after k − 1 steps the condition is true, after k steps it is false — two inequalities.
- Undoing integer division: x // q = y ⇔ q · y ≤ x ≤ q · y + q − 1; the number of suitable inputs is R − L + 1.
- For the largest number put big digits on the left, for the smallest put 9s on the right; check the answer with the options or a full search.