Count Digits

Q: 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 and O(1) space. For a 32-bit integer that is at most 10 steps.

Q: 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 is always exact.

Q: How do you count the digits of a negative number?

Take the absolute value first, then count as usual. String(-42) has three characters because the minus sign is not a digit. For the smallest 32-bit integer, take the absolute value in a 64-bit type, since it does not fit in 32 bits.

BeginnerMath and simulation

+10

Given a non-negative integer n, return how many digits it has when written in base 10 without leading zeros. Zero is written as a single 0, so it has one digit.

Function

countDigits(n: integer) → integer

ninteger: the non-negative integer to measure
Returnsinteger: the number of decimal digits in n

Constraints

0 ≤ n ≤ 2³¹-1

Examples

Input: n = 4096
Output: 4
Explanation: Integer division by 10 takes 4096 to 409, 40 and 4: three digits removed and one left, so the answer is 4.

Input: n = 0
Output: 1
Explanation: 0 is written with one digit. A loop that counts while the number is above 0 never runs here and returns 0 instead of 1.

Input: n = 100
Output: 3
Explanation: Zeros are digits too: 100 is written 1, 0, 0, so the answer is 3.

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.

0 of 3 opened

Solution

Each integer division by 10 removes one digit. Count the divisions until one digit is left, then add one for that digit. The bugs live at the edges: 0 has one digit, and a logarithm formula fails on 0 and a little below large powers of ten.

Write the number as text and count the characters

Intuition

Your language already writes n in decimal. Ask for that string and count its characters: 4096 becomes "4096", four characters, and 0 becomes "0", so zero needs no special case.

The conversion does one division per digit, so time and extra memory are both O(log n), at most 10 characters here.

Algorithm

Convert n to its decimal string with a function that never switches to scientific notation.
Count the characters of the string.
Return that count. For 0 the string is "0", so the answer is 1 with no extra check.

def countDigits(n):
    return len(str(n))

Divide by 10 until one digit is left

Intuition

Start the count at 1 and divide by 10 while n ≥ 10, adding 1 per division. Starting at 1 says every number has at least one digit, which is exactly the rule for 0, so no separate check is needed.

The loop runs at most 9 times, for 2147483647: O(log n) time. It keeps one counter and changes its own copy of n, so the extra space is O(1).

Algorithm

Set count = 1, for the digit that is always there.
While n ≥ 10, divide n by 10 with integer division and add 1 to count.
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

Counting from 0 while n > 0. It returns 0 for n = 0.
Using floor(log10(n)) + 1. It fails on 0, where the logarithm is minus infinity, and on 10^15-1, where double precision rounds the logarithm to exactly 15 and the formula says 16 digits.
Real division in JavaScript, Lua, PHP or R, where / keeps the fraction. A loop while n > 0 then runs 328 times for 4096. Use Math.floor, math.floor, intdiv or %/%.
Scientific notation in the string version. R writes as.character(1e5) as "1e+05"; use sprintf("%.0f", n). In Lua 5.3 and later, tostring(4096.0) keeps the .0; use string.format("%d", n).

Frequently asked questions3

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 and O(1) space. For a 32-bit integer that is at most 10 steps.

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 is always exact.

How do you count the digits of a negative number?

Take the absolute value first, then count as usual. String(-42) has three characters because the minus sign is not a digit. For the smallest 32-bit integer, take the absolute value in a 64-bit type, since it does not fit in 32 bits.

def countDigits(n):
    # Write code here

Test #1

Test #2

Test #3

Argument

n = 4096

Expected Output