Problem overview
The method noOfDigits receives a non-negative integer n up to one billion and returns how many digits it is written with. 542 has 3 digits, and 100 has 3 too, since zeros are digits. The number 0 counts as one digit.
Approach: count how many times you can divide by 10
With two int values, n / 10 drops the remainder and so removes the last digit: 542 becomes 54, then 5, then 0. That is three divisions for three digits. A loop that counts the divisions until the number reaches 0 counts the digits.
Zero is the one exception. It already equals 0, so the loop would run zero times and report no digits, but the answer must be 1. That is why the method handles it before the loop.
Step by step
- Return 1 when
nis 0. This is the special case the loop can't count. - Create
countas anintstarting at 0. - Write a
while (n > 0)loop that runs once per digit. - Add 1 to
countwithcount++. - Drop the last digit with
n = n / 10. Once every digit is gone,nis 0 and the loop stops. - Return
countafter the loop.
The solution in Java
class Solution {
public int noOfDigits(int n) {
if (n == 0) {
return 1;
}
int count = 0;
while (n > 0) {
count++;
n = n / 10;
}
return count;
}
}
Tracing n = 542: count goes 1, 2, 3 while n goes 54, 5, 0, then the method returns 3. For 1000000000 the loop runs ten times and returns 10.
Java details:
count++adds 1 tocount. It is shorthand forcount = count + 1.- Integer division. The result of
/on twointvalues is anint, so542 / 10is 54. - Changing the parameter. The method assigns to
n. That is legal, and the caller's variable keeps its value.
Another way: the length of the text
Java can answer the question in one line: String.valueOf(n).length() turns the number into text and counts its characters. It gives 3 for 542, and it even handles 0 without a special case, because "0" has length 1. The loop version in this lesson shows what that line does underneath, and it is the pattern to reuse when a problem asks for something about each digit, not just how many there are.
Why the loop must stop at 0
Each pass of the loop makes n smaller: the value is divided by 10 and the remainder is dropped. A number with one digit, such as 7, becomes 0 after a single division. Once n is 0, the condition n > 0 is false and the loop ends, so the number of passes equals the number of digits. This works for all non-negative values up to one billion, a 10-digit number, which needs exactly ten passes.
The check for 0 before the loop keeps the method's behaviour consistent with the statement. Powers of ten are the usual places where a counting loop is off by one, so they are worth trying.
n | Result | Result without the n == 0 check |
|---|---|---|
| 0 | 1 | 0 |
| 9 | 1 | 1 |
| 10 | 2 | 2 |
| 99 | 2 | 2 |
| 100 | 3 | 3 |
| 999999999 | 9 | 9 |
| 1000000000 | 10 | 10 |
The two columns differ only at 0, which shows that the early return is needed for that one input and for no other.
Complexity
Time: O(d), where d is the number of digits of n. The loop runs once per digit and each pass does a fixed amount of work. Since n is at most one billion, d is at most 10, so the method is effectively instant. In terms of the value, the work grows with the logarithm of n: a number ten times bigger needs just one more pass.
Space: O(1). The method keeps two integers, n and count, whatever the input.
Two traces
For n = 542, the pairs of count and n after each pass are (1, 54), (2, 5) and (3, 0). The answer is 3. For n = 100, they are (1, 10), (2, 1) and (3, 0), so the zeros are counted like any other digit and the answer is 3 again. In both cases the last pass leaves n at 0, which ends the loop.
Edge cases and common mistakes
- Zero. Without the first
if,noOfDigits(0)returns 0. - Zeros in the number.
100goes through 100, 10, 1 and reaches 0 after three divisions, so the answer is 3. - Starting
countat 1. That would work for 0 but be one too many for every other number. - Counting from 1 instead. Starting
countat 1 and looping whilen >= 10also works, with no special case for 0, since a number below 10 has exactly one digit. It gives 1, 1, 2, 2, 3, 3 and 10 for 0, 9, 10, 99, 100, 542 and 1000000000. The version in this lesson keeps the special case in plain view. - Using
while (n >= 0).nnever goes below 0 here, so the loop would run forever.
Testing
542gives3.100gives3.0gives1.1000000000gives10.
