Algorithms & Flowcharts — Worked Examples

7. Number-Crunching Algorithms

Number-Crunching Algorithms

These algorithms take an integer apart one digit at a time. Two tiny operations do almost all the work, so learn them cold:

• n % 10 (remainder when dividing by 10) gives the last digit. Example: 1234 % 10 = 4.
• n // 10 (whole-number division by 10) chops off the last digit. Example: 1234 // 10 = 123.

Repeating "grab last digit, then chop it off" peels a number down to nothing. Every trace table below has a % 10 column and a // 10 column so you can see each digit fall off.

Example (a): Count the digits in an integer

Problem

Read a non-negative integer and count how many digits it has (for example 4705 has 4 digits).

Pseudocode

INPUT n
SET count = 0
WHILE n > 0
    SET count = count + 1
    SET n = n // 10
OUTPUT count

Trace table

Sample input: n = 4705. Each iteration chops one digit off with // 10.

Iteration	n (before)	n > 0 ?	count after (+1)	n // 10	n (after)
start	4705	-	0	-	4705
1	4705	Yes	1	4705 // 10	470
2	470	Yes	2	470 // 10	47
3	47	Yes	3	47 // 10	4
4	4	Yes	4	4 // 10	0
exit	0	No	4	-	0

Digit count: 4.

In Python

n = 4705
count = 0
while n > 0:
    count = count + 1
    n = n // 10
print(count)

# Output:
# 4

Example (b): Sum of the digits of an integer

Problem

Add together all the digits of an integer (for 4705 that is 4+7+0+5 = 16).

Pseudocode

INPUT n
SET sum = 0
WHILE n > 0
    SET digit = n % 10
    SET sum = sum + digit
    SET n = n // 10
OUTPUT sum

Trace table

Sample input: n = 4705. The sum column is the accumulator.

Iteration	n (before)	digit = n % 10	sum = sum + digit	sum after	n = n // 10
start	4705	-	-	0	4705
1	4705	5	0 + 5	5	470
2	470	0	5 + 0	5	47
3	47	7	5 + 7	12	4
4	4	4	12 + 4	16	0
exit	0	-	-	16	0

Digit sum: 16.

In Python

n = 4705
total = 0
while n > 0:
    digit = n % 10
    total = total + digit
    n = n // 10
print(total)

# Output:
# 16

Example (c): Reverse an integer

Problem

Turn an integer back to front, so 1234 becomes 4321.

The trick: peel the last digit off the input with % 10, and push it onto a growing answer by doing rev = rev * 10 + digit. Multiplying rev by 10 shifts its digits left to make room for the new one.

Pseudocode

INPUT n
SET rev = 0
WHILE n > 0
    SET digit = n % 10
    SET rev = rev * 10 + digit
    SET n = n // 10
OUTPUT rev

Trace table

Sample input: n = 1234.

Iteration	n (before)	digit = n % 10	rev = rev*10 + digit	rev after	n = n // 10
start	1234	-	-	0	1234
1	1234	4	0*10 + 4	4	123
2	123	3	4*10 + 3	43	12
3	12	2	43*10 + 2	432	1
4	1	1	432*10 + 1	4321	0
exit	0	-	-	4321	0

Reversed number: 4321.

In Python

n = 1234
rev = 0
while n > 0:
    digit = n % 10
    rev = rev * 10 + digit
    n = n // 10
print(rev)

# Output:
# 4321

Example (d): Check if a number is a palindrome

Problem

A palindrome reads the same forwards and backwards (like 1221 or racecar). Decide whether an integer is a palindrome by reversing it and comparing with the original.

Pseudocode

INPUT n
SET original = n
SET rev = 0
WHILE n > 0
    SET rev = rev * 10 + (n % 10)
    SET n = n // 10
IF rev == original
    OUTPUT "palindrome"
ELSE
    OUTPUT "not a palindrome"

Trace table

Sample input: n = 1221 (we save original = 1221 first).

Iteration	n (before)	digit = n % 10	rev = rev*10 + digit	rev after	n = n // 10
start	1221	-	-	0	1221
1	1221	1	0*10 + 1	1	122
2	122	2	1*10 + 2	12	12
3	12	2	12*10 + 2	122	1
4	1	1	122*10 + 1	1221	0
exit	0	-	-	1221	0

Final check: rev (1221) == original (1221) is Yes, so 1221 is a palindrome.

In Python

n = 1221
original = n
rev = 0
while n > 0:
    rev = rev * 10 + (n % 10)
    n = n // 10
if rev == original:
    print("palindrome")
else:
    print("not a palindrome")

# Output:
# palindrome