Count Digits
Write a function that gets a non-negative integer n and returns how many digits it has when you write it in base 10 without leading zeros. Zero is written as a single 0, so it has one digit.
Function
- ninteger
- the non-negative integer to measure
- Returnsinteger
- the number of decimal digits in n
Constraints
0 ≤ n ≤ 231-1
Examples
- Input
- n = 4096
- Output
- 4
- Explanation
- Integer division by 10 takes
4096to409,40and4. That is three digits removed and one left, so the answer is4.
- Input
- n = 0
- Output
- 1
- Explanation
0is written with one digit. A loop that counts while the number is above 0 never runs here and would return0instead of1.
- Input
- n = 100
- Output
- 3
- Explanation
- The zeros are digits too:
100is written1,0,0, so the answer is3.
+16 hidden tests on Submit
Follow-up
Can you count the digits without a loop that runs once per digit, for example with a binary search over the powers of ten?
Hints
Open them one at a time. Each one gives away a little more.
What happens to the number of digits when you divide a number by 10 and throw away the remainder?
Each integer division by 10 removes exactly one digit from the end. Count how many divisions it takes to get down to a single digit.
Start a counter at 1 and divide by 10 while the number is at least 10, adding 1 each time. Starting at 1 also gives the right answer for
0.
Solution
The digit count is the number of times you can divide by 10 before one digit is left, plus that digit. The idea fits on one line; the work is in the edges. 0 has one digit, the count changes between 9 and 10, and a logarithm based formula breaks on 0 and, in floating point, a little below large powers of ten.
Write the number as text and count the characters
Intuition
Your language already knows how to write n in decimal. Ask it for that string and count the characters: 4096 becomes "4096", four characters. 0 becomes "0", one character, so zero needs no special case.
The conversion divides by 10 inside the library, once per digit, so the work is O(log n). The string holds one character per digit, which is O(log n) extra memory, at most 10 characters here.
The formatting has to be plain decimal. In R, as.character(1e5) gives "1e+05", five characters for a six-digit number, so format with sprintf("%.0f", n). In Lua 5.3 and later, tostring(4096.0) keeps the .0, while string.format("%d", n) writes the integer in every version.
Algorithm
- Convert
nto its decimal string with a function that never switches to scientific notation. - Count the characters of the string.
- Return that count. For
0the string is"0", so the answer is1with no extra check.
def countDigits(n):
return len(str(n))Divide by 10 until one digit is left
Intuition
Integer division by 10 removes the last digit: 4096 / 10 is 409. Each division takes away one digit, so the number of divisions it takes to reach a single digit, plus one for that last digit, is the answer. 4096 needs three divisions (409, 40, 4), so it has 4 digits.
Start the count at 1 and divide while n ≥ 10. Starting at 1 says that every number has at least one digit, which is exactly the rule for 0. The version people write first, counting while n > 0 from 0, returns 0 for n = 0 and needs a separate check.
The loop runs once per digit after the first, at most 9 times for 2147483647, so it takes O(log n) time. It keeps one counter and changes its own copy of n, which is O(1) extra space.
Algorithm
- Set
count = 1, for the digit that is always there. - While
n ≥ 10, dividenby 10 with integer division and add 1 tocount. - When one digit is left, return
count.
def countDigits(n):
count = 1 # every number, 0 included, has at least one digit
while n >= 10:
n //= 10
count += 1
return count
Pitfalls and edge cases
Every bug in this problem sits at an edge.
- Counting from 0 while
n > 0. It is right for every positive number and returns0forn = 0. - Using
floor(log10(n)) + 1. It fails on0, where the logarithm is minus infinity, and on large values a little below a power of ten: in double precisionlog10(10^15-1)rounds to exactly15, so the formula says 16 digits instead of 15. - Real division in a loop that runs while
n > 0. In JavaScript, Lua, PHP and R,/keeps the fraction, so4096shrinks toward 0 for 328 steps before it reaches it. UseMath.floor,math.floor,intdivor%/%. - Scientific notation in the string version: R writes
100000as"1e+05". - A minus sign counted as a digit. The input here is never negative, but
String(-42)has three characters, so a version for negative numbers takes the absolute value first.
Frequently asked questions4
How do you count the digits of a number without converting it to a string?
Divide it by 10 with integer division until one digit is left, counting the divisions, and add 1 for the last digit. 4096 becomes 409, 40, 4: three divisions, so 4 digits. The loop uses O(1) extra space.
Why does 0 have one digit?
Zero is written as the single character 0, so its decimal form has one digit. Code that counts divisions while the number is above 0 never runs for 0 and returns 0. Starting the counter at 1 and dividing while the number is at least 10 handles it with no special case.
Can you use log10 to count the digits of a number?
For a positive n the count is floor(log10(n)) + 1, but the logarithm is computed in floating point. It is undefined for 0, and close to a power of ten it can round the wrong way: log10(10^15-1) comes out as exactly 15 in double precision. Integer division gives the exact answer every time.
What is the time complexity of counting digits?
A number n has floor(log10(n)) + 1 digits, and the loop does one division per digit, so it runs in O(log n) time. For a 32-bit integer that is at most 10 steps.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
Python
def countDigits(n):
# Write code hereCase 1
Case 2
Case 3
Input
n = 4096
Expected
4