Take a number apart with division
A program stores 4096 as one value. The digits 4, 0, 9 and 6 are not kept anywhere, yet many problems are about digits: whether a number reads the same backwards, what its digits add up to, how it is written in binary. In this lesson we take numbers apart with one tool, division with a remainder. Later lessons use the same tool to find common divisors, to test whether a number is prime and to show that a sequence of remainders has to repeat.
Dividing 17 by 5 gives two results. The quotient is 3, the number of whole fives that fit into 17, and the remainder is 2, what is left over:
In Python the quotient is 17 // 5 and the remainder is 17 % 5. A single / is a different operator: 17 / 5 is the floating-point number 3.4.
items = 17
group_size = 5
print(items // group_size)
print(items % group_size)Prints 3, then 2.
Definition
For integers and , dividing by gives exactly one pair of integers and with and . The quotient is and the remainder is .
The remainder is always smaller than the number we divide by, so dividing by 5 can only leave 0, 1, 2, 3 or 4. A remainder of 5 or more would mean that another five still fits.
When the remainder is 0, we say that divides . Then is a divisor of , also called a factor, and is a multiple of . In code the test is a % b == 0: 12 % 3 is 0, so 3 divides 12, and 12 % 5 is 2, so 5 does not divide 12.
Dividing by 0 has no quotient and no remainder. Python raises ZeroDivisionError for both // and %.
Negative numbers in Python and C++
The definition covers only numbers that are not negative, and with a negative number the two languages give different answers. The difference starts with the quotient. When the exact quotient falls between two integers, Python's // rounds it down, to the smaller of the two, and C++'s / rounds it toward zero. Each language then makes % return the remainder that completes for its own quotient . For divided by 2 the exact quotient is :
| Expression | Python | C++ |
|---|---|---|
-7 // 2 (C++: -7 / 2) | -4 | -3 |
-7 % 2 | 1 | -1 |
-7 % 3 | 2 | -1 |
-1 % 5 | 4 | -1 |
With a positive number on the right of %, a Python remainder is never negative, and a C++ remainder is negative or 0 whenever the number on the left is negative.
The difference matters most when a remainder is used as a position in an array. Suppose five seats stand in a circle, numbered 0 to 4, and we move one seat to the left from seat i. The new seat is (i - 1) % 5, and from seat 0 it should come out as seat 4.
Python gives -1 % 5 = 4, so the expression is right for every seat. C++ gives for the same expression, which is why solutions written in C++ add the 5 back first and write (i - 1 + 5) % 5. In Python the added 5 changes nothing and can be left out.
Read a number one digit at a time
In decimal, each position is worth ten times the position to its right, so 4096 is 4 thousands, 0 hundreds, 9 tens and 6 ones. The thousands, hundreds and tens are all multiples of 10, and together they make 4090, which is 409 tens. What remains is the ones digit, 6, which is less than 10. That is a division by 10 with a remainder: the quotient is 409, the number without its last digit, and the remainder is 6, the last digit:
The remainder n % 10 is the last digit, and the quotient n // 10 is the number with that digit removed. Dividing the quotient by 10 again gives the next digit, and repeating until the quotient is 0 reads them all:
| n | Remainder: the last digit | Quotient: what is left |
|---|---|---|
| 4096 | 6 | 409 |
| 409 | 9 | 40 |
| 40 | 0 | 4 |
| 4 | 4 | 0 |
The digits come out from right to left, one for each division. A loop that adds each of them to a total computes the sum of the digits:
def digit_sum(n):
total = 0
while n > 0:
total += n % 10
n //= 10
return total
print(digit_sum(4096))
print(digit_sum(7))
print(digit_sum(0))For 0 the loop body never runs and the sum stays 0, which is the right answer. The loop expects a number that is not negative. For a negative one, we drop the sign first and read the digits of what remains.
Build a number from its digits
The loop above takes a number apart. Building a number from digits is the same step run backwards: we multiply what we have by 10, which moves every digit one place to the left and leaves a 0 in the ones place, and then add the new digit. Starting from 0 and feeding in 6, 9, 0 and 4, the digits of 4096 in the order the loop produced them, gives:
The result is 4096 with its digits reversed. A loop that does both steps each turn, taking the last digit off one number and appending it to another, reverses any number. That is enough to solve this problem:
You get an integer x. Return true if it reads the same from left to right as from right to left, and false otherwise.
Constraints
-
x
Sample 1 · Input
x = 121
Output
true
Sample 2 · Input
x = -121
Output
false
Sample 3 · Input
x = 10
Output
false
A number reads the same in both directions when it is equal to its own reversal, as 121 is. The reversal of 10 would be written 01, and a number does not keep a leading zero, so the reversed value is 1 and 10 is not a palindrome. A negative number has its minus sign at the front only, so it never reads the same backwards, and the function returns false for it before the loop.
def is_palindrome(x):
if x < 0:
return False
original = x
reversed_x = 0
while x > 0:
reversed_x = reversed_x * 10 + x % 10
x //= 10
return reversed_x == original
print(is_palindrome(121))
print(is_palindrome(-121))
print(is_palindrome(10))In Python, comparing str(x) with str(x)[::-1] gives the same answers. The judge's follow-up asks for a solution that does not convert the number to a string, and the arithmetic version is one. It also works in any base, with the base in place of 10.
Digits in another base
The digit loop used the number 10 only because a decimal position is worth ten times its neighbour. In base , each position is worth times the position to its right, and a digit is a value from 0 to . Base 2, or binary, has the digits 0 and 1 and positions worth 1, 2, 4, 8 and so on. To write 13 in base 2, we run the digit loop with 2 in place of 10:
The remainders are the binary digits from right to left, so 13 in base 2 is 1101: one 8, one 4, no 2 and one 1. Going back is the building step with 2 in place of 10. Reading 1101 from the left gives 1, then , then , then .
Here is the conversion for any base up to 10, where every digit is one of the characters 0 to 9. The loop collects the digits last first, so the function reverses them at the end:
def to_base(n, b):
if n == 0:
return '0'
digits = []
while n > 0:
digits.append(str(n % b))
n //= b
return ''.join(reversed(digits))
print(to_base(13, 2))
print(to_base(4096, 8))
print(to_base(0, 2))The function returns early for 0 because the loop would not run for it, and the result would be an empty string. 4096 in base 8 is 10000 because .
Cost of the digit loop
- Read, sum or reverse the decimal digits of $n$
- One division per digit: 4 for 4096, at most 10 for a number below and at most 19 for a number below .
- Write $n$ in base $b$
- One division per digit in that base: 4 for 13 in base 2, and at most 31 for a number below .
Each turn divides by the base, and the loop ends when nothing is left. A useful way to think about the logarithm is as the number of times can be divided by before the result is 1 or less. The loop makes about that many turns, one for each digit. The count grows by one each time becomes times larger: 999 has three decimal digits and 1000 has four. Logarithms in two bases differ only by a constant factor, since is divided by about 3.32, so in every base the loop is .
A base with no zero: spreadsheet column labels
Spreadsheets label their columns A to Z, then AA, AB and so on to AZ, then BA. The labels count in 26s, like a number in base 26, with one difference from the bases above: the 26 letters stand for the values 1 to 26, and no letter stands for 0. Two judge problems convert between a label and its column number. The missing zero causes trouble only when we go from a number to its label.
You get a spreadsheet column label columnTitle in capital letters. Columns are labelled A to Z, then AA, AB, ..., AZ, BA and so on. Return the column number of the label, counting A as 1.
Constraints
-
columnTitle.length columnTitleholds only capital English letterscolumnTitleis in the range ["A", "FXSHRXW"]
Sample 1 · Input
columnTitle = "A"
Output
1
Sample 2 · Input
columnTitle = "AB"
Output
28
Sample 3 · Input
columnTitle = "ZY"
Output
701
From a label to its number is the building step with 26 in place of 10 and the letter values A = 1, B = 2, up to Z = 26:
def title_to_number(title):
number = 0
for ch in title:
number = number * 26 + (ord(ch) - ord('A') + 1)
return number
print(title_to_number("AB"))
print(title_to_number("ZY"))
print(title_to_number("FXSHRXW"))ord(ch) - ord('A') is 0 for A and 25 for Z, so adding 1 gives the letter's value.
The last call converts FXSHRXW, the largest label the problem allows. It is column 2,147,483,647, which is .
You get a positive integer columnNumber. Return its spreadsheet column label: the previous problem in reverse.
Constraints
-
columnNumber
Sample 1 · Input
columnNumber = 1
Output
"A"
Sample 2 · Input
columnNumber = 28
Output
"AB"
Sample 3 · Input
columnNumber = 701
Output
"ZY"
From a number to its label is the digit loop with 26 in place of 10, and here the missing zero gets in the way. Consider column 26, whose label is Z. Dividing gives : a remainder of 0, which no letter stands for, and a quotient of 1 still to convert, although Z is a single letter.
The remainder of a division by 26 is a value from 0 to 25, but the value of a letter is from 1 to 26. Subtracting 1 from the number before dividing lines the two ranges up.
Take a label whose last letter has the value , and let be the column number of the label without that letter. Then the column number is : for AB, the B has , A alone is column , and . One less than that is , and is between 0 and 25. So after the subtraction, the remainder is the last letter counted from A = 0, and the quotient is , the column number of the letters before it.
For 26, subtracting 1 leaves : the letter is Z, and the quotient 0 ends the loop. For 28, subtracting 1 leaves , which is the letter B with the quotient 1 still to convert. Subtracting 1 from that leaves 0, the letter A, and a quotient of 0. The letters came out as B and then A, last first, so the label is AB.
def number_to_title(n):
letters = []
while n > 0:
n -= 1
letters.append(chr(ord('A') + n % 26))
n //= 26
return ''.join(reversed(letters))
print(number_to_title(28))
print(number_to_title(26))
print(number_to_title(701))Step through each division
Step through the digit loop one division at a time. 4096 in base 10 and 13 in base 2 are the conversions worked above, and the column examples subtract 1 before each division. Column 26, no subtracting 1 leaves the subtraction out and counts A as 0, and it produces BA for the column whose label is Z.
Common mistakes with digits and remainders
Using the digits in the order the loop produces them.
- Where it breaks
- Printing each
n % 2as it is computed prints1011for 13, which is the binary for 11. The loop yields the last digit first. - The fix
- Collect the digits and reverse them, as
to_basedoes.
Building a string of digits without handling 0 first.
- Where it breaks
- The body of
while n > 0never runs for 0, so the string comes out empty instead of"0". - The fix
- Return
"0"before the loop.
Reading the last digit of a negative number with
% 10.- Where it breaks
- The last digit of is 7, but
-47 % 10is 3 in Python and-7in C++. - The fix
- Drop the sign first, then read the digits of what remains.
Recall Write 45 in base 2 with the digit loop. How many divisions does it take?
The divisions are , , , , and . Read from the last remainder to the first, 45 is 101101 in base 2, which is . It takes six divisions, one for each binary digit.
Recall Which column has the label ZZ, and what is the label of the column after it?
ZZ is , so the next column is 703. Subtracting 1 leaves , the letter A with 27 still to convert. Subtracting 1 from 27 leaves , another A with 1 still to convert. Subtracting 1 from that leaves 0, a third A. Column 703 is AAA, the first label with three letters.