Count Digits

Q: Qual é a complexidade de tempo para contar dígitos?

Um número n tem floor(log10(n)) + 1 dígitos, e o loop faz uma divisão por dígito, então é executado em tempo O(log n) e espaço O(1) . Para um inteiro de 32 bits, são no máximo 10 etapas.

Q: Você pode usar log10 para contar os dígitos de um número?

Para um n positivo, a contagem é floor(log10(n)) + 1 , mas o logaritmo é calculado em ponto flutuante. Ele é indefinido para 0 e, próximo a uma potência de dez, pode arredondar na direção errada: log10(10^15-1) resulta exatamente em 15 com precisão dupla. A divisão inteira é sempre exata.

InicianteMatemática e simulação

+10

Dado um inteiro não negativo n, retorne quantos dígitos ele tem quando escrito na base 10 sem zeros à esquerda. Zero é escrito como um único 0, portanto tem um dígito.

Função

countDigits(n: integer) → integer

ninteger: o número inteiro não negativo a ser medido
Retornainteger: o número de dígitos decimais em n

Restrições

0 ≤ n ≤ 2³¹-1

Exemplos

Entrada: n = 4096
Saída: 4
Explicação: A divisão inteira por 10 transforma 4096 em 409, 40 e 4: três dígitos removidos e um restante, então a resposta é 4.

Entrada: n = 0
Saída: 1
Explicação: 0 é escrito com um dígito. Um loop que conta enquanto o número é maior que 0 nunca é executado aqui e retorna 0 em vez de 1.

Entrada: n = 100
Saída: 3
Explicação: Os zeros também são algarismos: 100 é escrito como 1, 0, 0, então a resposta é 3.

Para ir além

Você consegue contar os dígitos sem usar um loop que é executado uma vez por dígito, por exemplo, com uma busca binária entre as potências de dez?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Cada divisão inteira por 10 remove um dígito. Conte as divisões até restar um dígito e, então, some um por esse dígito. Os bugs aparecem nos casos extremos: 0 tem um dígito, e uma fórmula com logaritmo falha em 0 e um pouco abaixo das grandes potências de dez.

Escreva o número como texto e conte os caracteres

Intuição

Sua linguagem já escreve n em decimal. Peça essa string e conte seus caracteres: 4096 se torna "4096", quatro caracteres, e 0 se torna "0", então zero não precisa de um caso especial.

A conversão faz uma divisão por dígito, então o tempo e a memória extra são ambos O(log n), no máximo 10 caracteres aqui.

Algoritmo

Converta n para sua representação decimal em string usando uma função que nunca muda para notação científica.
Conte os caracteres da string.
Retorne essa contagem. Para 0, a string é "0", então a resposta é 1, sem nenhuma verificação extra.

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

Divida por 10 até restar um dígito

Intuição

Comece a contagem em 1 e divida por 10 enquanto n ≥ 10, adicionando 1 a cada divisão. Começar em 1 indica que todo número tem pelo menos um dígito, que é exatamente a regra para 0, então não é necessária uma verificação separada.

O loop executa no máximo 9 vezes, para 2147483647: tempo O(log n). Ele mantém um contador e altera sua própria cópia de n, então o espaço extra é O(1).

Algoritmo

Defina count = 1, para o dígito que está sempre presente.
Enquanto n ≥ 10, divida n por 10 usando divisão inteira e adicione 1 a count.
Quando restar um dígito, retorne count.

def countDigits(n):
    count = 1  # every number, 0 included, has at least one digit
    while n >= 10:
        n //= 10
        count += 1
    return count

Armadilhas e casos extremos

Contar a partir de 0 enquanto n > 0. Retorna 0 para n = 0.
Usar floor(log10(n)) + 1. Isso falha com 0, cujo logaritmo é menos infinito, e com 10^15-1, quando a precisão dupla arredonda o logaritmo para exatamente 15 e a fórmula indica 16 dígitos.
Divisão real em JavaScript, Lua, PHP ou R, em que / mantém a parte fracionária. Um loop enquanto n > 0 então executa 328 vezes para 4096. Use Math.floor, math.floor, intdiv ou %/%.
Notação científica na versão com string. R escreve as.character(1e5) como "1e+05"; use sprintf("%.0f", n). No Lua 5.3 e posteriores, tostring(4096.0) mantém o .0; use string.format("%d", n).

Perguntas frequentes3

Qual é a complexidade de tempo para contar dígitos?

Um número n tem floor(log10(n)) + 1 dígitos, e o loop faz uma divisão por dígito, então é executado em tempo O(log n) e espaço O(1). Para um inteiro de 32 bits, são no máximo 10 etapas.

Você pode usar log10 para contar os dígitos de um número?

Para um n positivo, a contagem é floor(log10(n)) + 1, mas o logaritmo é calculado em ponto flutuante. Ele é indefinido para 0 e, próximo a uma potência de dez, pode arredondar na direção errada: log10(10^15-1) resulta exatamente em 15 com precisão dupla. A divisão inteira é sempre exata.

Como contar os dígitos de um número negativo?

Primeiro, obtenha o valor absoluto e depois conte normalmente. String(-42) tem três caracteres porque o sinal de menos não é um dígito. Para o menor inteiro de 32 bits, obtenha o valor absoluto em um tipo de 64 bits, pois ele não cabe em 32 bits.

def countDigits(n):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumento

n = 4096

Saída Esperada