15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
A number n is divisible by d exactly when n mod d = 0. Shortcuts read only some digits: the last digit for 2, 5 and 10, the last two for 4, the digit sum for 3 and 9. For any positive d, scan the digits once, keeping remainder = (remainder × 10 + digit) mod d.
| Definition | d divides n exactly when n mod d = 0, for nonzero d |
|---|---|
| Divisible by 2, 5, 10 | Check the last digit, because 10 mod each of them is 0 |
| Divisible by 4 | Check the last two digits, because 100 mod 4 = 0 |
| Divisible by 3, 9 | Check the digit sum, because every power of 10 leaves remainder 1 |
| Any divisor d | remainder = (remainder × 10 + digit) mod d; O(L) time for L digits, O(1) space |
The lesson uses modular arithmetic from fast exponentiation: after an arithmetic step, keep only the remainder modulo a divisor without changing the final divisibility decision.
For a nonzero integer d:
For example, , so 3 divides 12. But , so 3 does not divide 14.
A decimal number has place values:
The rules in the lesson come from the remainders of powers of 10 for a particular divisor.
For the digit-string utility, assume:
0 through 9.For example, "04" represents the same value as "4" for divisibility purposes.
Determine whether decimal string "12348" is divisible by 3, 4, and 9.
12348: the digit sum 18 decides divisibility by 3 and 9, and the last two digits 48 decide divisibility by 4, because 100 × 123 adds nothing mod 4.
Start with its decimal form:
For divisibility by 3 and 9, add the digits:
Test that sum:
So "12348" is divisible by 3.
So "12348" is divisible by 9.
For divisibility by 4, inspect the final two decimal digits:
So "12348" is also divisible by 4.
A number can be written as:
where r is its last decimal digit.
Because 10 is divisible by 2, 5, and 10, the term contributes remainder 0 for each divisor. Only r matters.
0, 2, 4, 6, or 8.0 or 5.0.For "12348", the last digit is 8. It is even, so the number is divisible by 2. It is not 0 or 5, so it is not divisible by 5. It is not 0, so it is not divisible by 10.
Separate a decimal number into everything except its final two digits and its final two digits:
Here, r is between 0 and 99. For "12348":
Since:
we get:
The earlier digits have remainder 0 modulo 4. The last two digits are enough.
Modulo 3:
So every power of 10 also has remainder 1:
Then:
Modulo 9:
Every power of 10 has remainder 1 modulo 9, so the number and its digit sum have the same remainder modulo 9. The number and its digit sum also have the same remainder modulo 3.
For "12348", the digit sum is 18. Its remainder is 0 modulo both 3 and 9.
A digit string may be longer than a machine integer can hold. Scan one digit at a time instead of constructing the whole number.
Before scanning, the running remainder is:
| Scanned prefix | Numeric value | Remainder modulo 3 |
|---|---|---|
| empty | 0 | 0 |
Append digit 1.
Append digit 2.
Append digit 3.
Append digit 4.
Append digit 8.
The remainder sequence is:
The final remainder is 0, so "12348" is divisible by 3.
While scanning a digit string, keep one value named remainder.
After scanning any prefix, remainder equals the canonical remainder of the numeric value represented by that prefix modulo the chosen divisor.
For example, while scanning "12348" modulo 3:
| Prefix scanned | Prefix value | Stored remainder | Prefix value mod 3 |
|---|---|---|---|
"" | 0 | 0 | 0 |
"1" | 1 | 1 | 1 |
"12" | 12 | 0 | 0 |
"123" | 123 | 0 | 0 |
"1234" | 1234 | 1 | 1 |
"12348" | 12348 | 0 | 0 |
The stored value always matches the actual remainder. The matching relationship is the loop invariant.
The algorithm does not need the full prefix value. It needs only the prefix's remainder.
Suppose the digits scanned so far represent a prefix value p. Append a digit x.
The new prefix value is:
Suppose the stored remainder is:
Because p and r have the same remainder modulo d, multiplying each by 10 preserves that equivalence:
Adding x also preserves it:
Therefore update the stored remainder with:
After the final digit, test:
The general scan works for divisor 3, divisor 4, divisor 9, and any other positive divisor. The specialized rules inspect fewer digits when their conditions apply:
| Divisor | What to inspect | Reason |
|---|---|---|
| 2 | Last digit | |
| 5 | Last digit | |
| 10 | Last digit | |
| 4 | Last two digits | |
| 3 | Digit sum | |
| 9 | Digit sum |
Each specialized rule follows from modular equivalence.
isDivisibleDecimalString validates the input and scans it without constructing the full numeric value.
Input: s, a nonempty string; d, a positive integer
Returns: true if the decimal value represented by s is divisible by d; otherwise false
Mutation: Does not modify s or d
Boundary behavior: Leading zeros are valid. An empty string, a nondigit character, or a nonpositive divisor is invalid.
11 function isDivisibleDecimalString(s, d):
22 if d <= 0:
33 raise InvalidDivisor
44
55 if length(s) = 0:
66 raise InvalidDecimalString
77
88 remainder ← 0
99
1010 for each character ch in s from left to right:
1111 if ch < '0' or ch > '9':
1212 raise InvalidDecimalString
1313
1414 digit ← decimalDigitValue(ch)
1515 remainder ← (remainder × 10 + digit) mod d
1616
1717 return remainder = 0Helper contract:
1decimalDigitValue(ch)
2Input: one character ch where '0' <= ch <= '9'
3Returns: the integer from 0 through 9 represented by ch
4Mutation: none
5Precondition: ch is a decimal digitThe test at line 11 establishes the helper's precondition before line 14 calls it.
Use the original input "12348".
Call:
1isDivisibleDecimalString("12348", 3)3 <= 0 is false.length("12348") = 0 is false.remainder ← 0.Now execute lines 10 through 15 once for every character.
| Character at line 10 | Line 11 valid? | Line 14 digit | Line 15 calculation | New remainder |
|---|---|---|---|---|
'1' | yes | 1 | 1 | |
'2' | yes | 2 | 0 | |
'3' | yes | 3 | 0 | |
'4' | yes | 4 | 1 | |
'8' | yes | 8 | 0 |
remainder = 0 is true.true.So "12348" is divisible by 3.
Call:
1isDivisibleDecimalString("12348", 4)remainder ← 0.| Character | Line 14 digit | Line 15 calculation | New remainder |
|---|---|---|---|
'1' | 1 | 1 | |
'2' | 2 | 0 | |
'3' | 3 | 3 | |
'4' | 4 | 2 | |
'8' | 8 | 0 |
true.So "12348" is divisible by 4.
Call:
1isDivisibleDecimalString("12348", 9)remainder ← 0.| Character | Line 14 digit | Line 15 calculation | New remainder |
|---|---|---|---|
'1' | 1 | 1 | |
'2' | 2 | 3 | |
'3' | 3 | 6 | |
'4' | 4 | 1 | |
'8' | 8 | 0 |
true.So "12348" is divisible by 9.
We prove that isDivisibleDecimalString(s, d) returns true exactly when the decimal value of s is divisible by positive integer d.
Before the loop, line 8 sets:
The scanned prefix is empty, whose numeric value is 0. Since:
the stored remainder equals the remainder of the scanned prefix. The invariant holds before the first iteration.
Assume the invariant holds before an iteration. Let:
p be the numeric value of the prefix already scanned.remainder = p mod d.digit be the value of the next character.Appending the digit changes the prefix value from p to:
Line 15 computes:
Since:
then:
So the updated remainder equals the remainder of the newly scanned prefix. The invariant is preserved.
The loop scans every character in s. When it ends, the scanned prefix is the entire string, so remainder equals the numeric value of s modulo d.
Line 17 returns true exactly when:
By the definition of divisibility, d divides the number represented by s exactly when the remainder is 0.
Therefore, the algorithm is correct.
Let L be the number of digits in the input string.
Each does a constant amount of work, so each takes:
A digit-sum scan visits each of the L digits once. A streaming-remainder scan also visits each digit once.
For each digit, the streaming scan performs constant work:
d.That is L iterations with constant work per iteration:
The scan stores only:
So its auxiliary space is:
The input string itself is not auxiliary space. The streaming method does not construct the full numeric value, even when the string has more digits than a machine integer can represent.
Incorrect assumption: “A number is divisible by 4 when its last digit is divisible by 4.”
Exposing input: 12
Wrong decision: The last digit is 2, and 2 is not divisible by 4, so this rule says 12 is not divisible by 4.
Actual result:
Correction: Inspect the last two digits. Here, 12 mod 4 = 0.
Incorrect line or assumption:
1return digitSum is evenExposing input: 14
The digit sum is:
The incorrect test makes a decision based on whether 5 is odd. Parity does not determine divisibility by 3.
Correction: Test the digit sum modulo 3:
So 14 is not divisible by 3.
Incorrect line:
1remainder ← (remainder + digit) mod dExposing input: "12" with divisor 7
Incorrect states:
remainder = 01: 2: The incorrect update produces remainder 3.
But:
Correction: Appending a digit shifts the previous value one decimal place:
1remainder ← (remainder × 10 + digit) mod dThen:
1: 2: Incorrect assumption: “Zero is not divisible by a nonzero number.”
Exposing input: "0" with divisor 5
Wrong result: false
But:
Correction: "0" is divisible by every nonzero divisor used in this lesson.
| Input | Divisor | Expected behavior |
|---|---|---|
"0" | 5 | Return true |
"5" | 5 | Return true |
"5" | 2 | Return false |
"5" | 10 | Return false |
"04" | 4 | Return true |
"100" | 4 | Return true, because final two digits are 00 |
"123456789" | 3 | Return true, because digit sum is 45 |
"123456789" | 9 | Return true, because digit sum is 45 |
"" | 3 | Reject as an invalid decimal string |
"12a" | 3 | Reject as an invalid decimal string |
Implement:
1isDivisibleDecimalString(s, d)Objective: For a nonempty decimal-digit string s and positive integer d, use the streaming update
and return whether the final remainder is zero.
Your implementation contract will be tested with:
"04",1def is_divisible_decimal_string(s, d):
2 if d <= 0:
3 raise ValueError("divisor must be positive")
4 if not s:
5 raise ValueError("empty digit string")
6 remainder = 0
7 for ch in s:
8 if ch < "0" or ch > "9":
9 raise ValueError("not a decimal digit")
10 remainder = (remainder * 10 + (ord(ch) - ord("0"))) % d
11 return remainder == 0
12
13for d in (3, 4, 9, 5):
14 print(f"12348 % {d} == 0: {str(is_divisible_decimal_string('12348', d)).lower()}")1public class Main {
2 static boolean isDivisibleDecimalString(String s, int d) {
3 if (d <= 0) throw new IllegalArgumentException("divisor must be positive");
4 if (s.isEmpty()) throw new IllegalArgumentException("empty digit string");
5 int remainder = 0;
6 for (char ch : s.toCharArray()) {
7 if (ch < '0' || ch > '9') throw new IllegalArgumentException("not a decimal digit");
8 remainder = (remainder * 10 + (ch - '0')) % d; // remainder stays below d, so no overflow
9 }
10 return remainder == 0;
11 }
12
13 public static void main(String[] args) {
14 for (int d : new int[]{3, 4, 9, 5}) {
15 System.out.println("12348 % " + d + " == 0: " + isDivisibleDecimalString("12348", d));
16 }
17 }
18}1#include <iostream>
2#include <stdexcept>
3#include <string>
4using namespace std;
5
6bool isDivisibleDecimalString(const string& s, int d) {
7 if (d <= 0) throw invalid_argument("divisor must be positive");
8 if (s.empty()) throw invalid_argument("empty digit string");
9 int remainder = 0;
10 for (char ch : s) {
11 if (ch < '0' || ch > '9') throw invalid_argument("not a decimal digit");
12 remainder = (remainder * 10 + (ch - '0')) % d; // remainder stays below d, so no overflow
13 }
14 return remainder == 0;
15}
16
17int main() {
18 for (int d : {3, 4, 9, 5}) {
19 cout << "12348 % " << d << " == 0: " << boolalpha << isDivisibleDecimalString("12348", d) << endl;
20 }
21}1function isDivisibleDecimalString(s, d) {
2 if (d <= 0) throw new Error("divisor must be positive");
3 if (s.length === 0) throw new Error("empty digit string");
4 let remainder = 0;
5 for (const ch of s) {
6 if (ch < "0" || ch > "9") throw new Error("not a decimal digit");
7 remainder = (remainder * 10 + (ch.charCodeAt(0) - 48)) % d;
8 }
9 return remainder === 0;
10}
11
12for (const d of [3, 4, 9, 5]) {
13 console.log(`12348 % ${d} == 0: ${isDivisibleDecimalString("12348", d)}`);
14}Add the digits and test the sum. Since 10 leaves remainder 1 modulo 3 and modulo 9, every power of 10 does too, so a number and its digit sum share a remainder. For 12348 the sum is 18, divisible by both.
Because 10 is not divisible by 4. Take 12: its last digit 2 is not divisible by 4, yet 12 = 3 × 4. The number 100 is divisible by 4, so only the last two digits matter.
Scan the digit string left to right and update remainder = (remainder × 10 + digit) mod d. You never build the full number. It takes O(L) time for L digits and O(1) extra space.
Appending a digit shifts the earlier value one decimal place. Using (remainder + digit) gives 3 for 12 with divisor 7, but 12 mod 7 is 5. The shift gives (0 × 10 + 1) then (1 × 10 + 2) = 12, remainder 5.
Yes, by every nonzero number. 0 mod 5 = 0, so the string "0" with divisor 5 returns true.
No. Divisibility by 3 depends on the digit sum modulo 3, not on whether the sum is even. For 14 the sum is 5, and 5 mod 3 = 2, so 14 is not divisible by 3.