Count Digits

Q: Por que 0 tem um dígito?

Zero é escrito como o caractere único 0 , então sua forma decimal tem um dígito. O código que conta as divisões enquanto o número é maior que 0 nunca é executado para 0 e retorna 0. Começar o contador em 1 e dividir enquanto o número for pelo menos 10 lida com isso sem nenhum caso especial.

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, perto de uma potência de dez, pode ser arredondado para o lado errado: log10(10^15-1) resulta exatamente em 15 em precisão dupla. A divisão inteira fornece a resposta exata todas as vezes.

Q: Qual é a complexidade de tempo de 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) . Para um inteiro de 32 bits, são no máximo 10 etapas.

InicianteMatemática e simulação

+10

Escreva uma função que recebe um número inteiro não negativo n e retorna 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 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. Isso significa que três dígitos foram removidos e um restou, 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 neste caso e retornaria 0 em vez de 1.

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

+16 testes ocultos ao enviar

Para ir além

Você consegue contar os dígitos sem um loop que é executado uma vez por dígito, por exemplo, usando 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

A quantidade de dígitos é o número de vezes que você pode dividir por 10 antes que reste um dígito, mais esse dígito. A ideia cabe em uma linha; o trabalho está nos casos extremos. 0 tem um dígito, a contagem muda entre 9 e 10, e uma fórmula baseada em logaritmo falha com 0 e, em ponto flutuante, um pouco abaixo de potências grandes de 10.

Escreva o número por extenso e conte os caracteres

Intuição

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

A conversão divide por 10 dentro da biblioteca, uma vez por dígito, então o trabalho é O(log n). A string contém um caractere por dígito, o que representa O(log n) de memória extra, no máximo 10 caracteres neste caso.

A formatação precisa ser em decimal simples. Em R, as.character(1e5) retorna "1e+05", cinco caracteres para um número de seis dígitos, então formate com sprintf("%.0f", n). No Lua 5.3 e versões posteriores, tostring(4096.0) mantém o .0, enquanto string.format("%d", n) escreve o inteiro em todas as versões.

Algoritmo

Converta n em sua representação decimal como 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

A divisão inteira por 10 remove o último dígito: 4096 / 10 é 409. Cada divisão remove um dígito, então a resposta é o número de divisões necessárias para chegar a um único dígito, mais um por esse último dígito. 4096 precisa de três divisões (409, 40, 4), portanto tem 4 dígitos.

Comece a contagem em 1 e divida enquanto n ≥ 10. Começar em 1 significa que todo número tem pelo menos um dígito, o que corresponde exatamente à regra para 0. A versão que as pessoas escrevem primeiro, contando a partir de 0 enquanto n > 0, retorna 0 para n = 0 e precisa de uma verificação separada.

O loop é executado uma vez para cada dígito após o primeiro, no máximo 9 vezes para 2147483647, então leva tempo O(log n). Ele mantém um contador e altera sua própria cópia de n, o que ocupa O(1) de espaço extra.

Algoritmo

Defina count = 1, para o dígito que está sempre presente.
Enquanto n ≥ 10, divida n por 10 usando divisão inteira e some 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

Cada erro neste problema está em um caso extremo.

Contar a partir de 0 enquanto n > 0. Isso funciona para todo número positivo e retorna 0 para n = 0.
Usar floor(log10(n)) + 1. Isso falha para 0, cujo logaritmo é menos infinito, e para valores grandes um pouco abaixo de uma potência de dez: em precisão dupla, log10(10^15-1) é arredondado exatamente para 15, então a fórmula retorna 16 dígitos em vez de 15.
Divisão real em um loop que executa enquanto n > 0. Em JavaScript, Lua, PHP e R, / mantém a fração, então 4096 diminui em direção a 0 por 328 etapas antes de chegar lá. Use Math.floor, math.floor, intdiv ou %/%.
Notação científica na versão com string: R escreve 100000 como "1e+05".
Contar o sinal de menos como um dígito. A entrada aqui nunca é negativa, mas String(-42) tem três caracteres, então uma versão para números negativos primeiro calcula o valor absoluto.

Perguntas frequentes4

Como contar os dígitos de um número sem convertê-lo em uma string?

Divida por 10 usando divisão inteira até restar um dígito, contando as divisões, e some 1 para o último dígito. 4096 se torna 409, 40, 4: três divisões, portanto, 4 dígitos. O loop usa espaço extra O(1).

Por que 0 tem um dígito?

Zero é escrito como o caractere único 0, então sua forma decimal tem um dígito. O código que conta as divisões enquanto o número é maior que 0 nunca é executado para 0 e retorna 0. Começar o contador em 1 e dividir enquanto o número for pelo menos 10 lida com isso sem nenhum caso especial.

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, perto de uma potência de dez, pode ser arredondado para o lado errado: log10(10^15-1) resulta exatamente em 15 em precisão dupla. A divisão inteira fornece a resposta exata todas as vezes.

Qual é a complexidade de tempo de 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). Para um inteiro de 32 bits, são no máximo 10 etapas.

Python

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

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

n = 4096

Esperado