Steps to Reduce a Number to Zero

Q: Qual é a complexidade temporal de reduzir um número a zero?

Executar o processo leva tempo O(log n) , porque pelo menos a cada segundo passo o número é reduzido à metade. Para n = 2^31 - 1 , são 61 passos. Contar os dígitos binários com instruções de bits integradas é O(1) .

Q: Qual é a fórmula para o número de passos?

Para n > 0 , a resposta é o comprimento de n em binário, menos um, mais o número de bits 1. Cada bit 1 custa uma subtração, e cada dígito abaixo do 1 inicial custa uma divisão por 2. Para n = 0 , a resposta é 0 .

Q: Qual número abaixo de 2^31 leva mais etapas?

2^31 - 1 , que corresponde a trinta e um algarismos 1 em binário. São necessárias 31 subtrações e 30 divisões pela metade, 61 etapas no total. Nenhum número menor tem tantos dígitos e tantos algarismos 1 ao mesmo tempo.

InicianteManipulação de bits Matemática e simulação

+10

Comece com um número inteiro não negativo n e repita uma regra até que ele chegue a 0: se o número for par, divida-o por 2; se for ímpar, subtraia 1. Cada aplicação da regra corresponde a um passo. Retorne o número de passos necessários.

Função

numberOfSteps(n: integer) → integer

ninteger: o número inicial
Retornainteger: o número de etapas até que o número chegue a 0

Restrições

0 ≤ n ≤ 2³¹ - 1

Exemplos

Entrada: n = 14
Saída: 6
Explicação: O número vai de 14 → 7 → 6 → 3 → 2 → 1 → 0: três divisões pela metade e três subtrações, 6 passos.

Entrada: n = 8
Saída: 4
Explicação: 8 → 4 → 2 → 1 → 0. Uma potência de dois é dividida pela metade três vezes e precisa de uma subtração no final, 4 etapas.

Entrada: n = 123
Saída: 12
Explicação: 123 é 1111011 em binário: sete dígitos e seis 1s. Os seis 1s custam seis subtrações, e os seis dígitos abaixo do 1 inicial custam seis divisões por 2: 12 etapas.

+12 testes ocultos ao enviar

Para ir além

Suponha que um número ímpar também possa aumentar em 1 em vez de diminuir. Qual é o menor número de etapas para chegar a 0 e qual escolha é a certa para 15?

Dicas

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

0 de 3 abertas

Solução

Executar a regra já é rápido: cada divisão pela metade corta o número ao meio, então até mesmo 2^31 - 1 precisa de apenas 61 etapas. A parte interessante é ver o que a regra faz com os dígitos binários. Dividir pela metade remove o último dígito, e subtrair 1 de um número ímpar transforma seu último 1 em um 0. Portanto, a resposta é o número de dígitos mais o número de 1s, menos um.

Execute o processo

Intuição

Faça o que a instrução diz. Enquanto n for maior que 0, divida-o pela metade se for par, subtraia 1 se for ímpar e conte a etapa. Para 14, o loop visita 7, 6, 3, 2, 1 e 0, em seis etapas.

O loop é curto porque uma subtração sempre torna um número ímpar em par, então pelo menos a cada duas etapas ocorre uma divisão pela metade. Um número menor que 2^31 é dividido pela metade no máximo 30 vezes antes de chegar a 1 e, com uma subtração antes de cada divisão pela metade e uma no final, o loop é executado no máximo 61 vezes.

A entrada 0 não precisa de um caso especial: a condição do loop falha imediatamente e a resposta é 0.

Algoritmo

Defina steps como 0.
Enquanto n > 0: se n for par, defina n como n / 2; caso contrário, como n-1.
Adicione 1 a steps a cada vez.
Retorne steps.

def numberOfSteps(n):
    steps = 0
    while n > 0:
        if n % 2 == 0:
            n //= 2
        else:
            n -= 1
        steps += 1
    return steps

Conte os dígitos binários

Intuição

Acompanhe o processo em binário. 14 é 1110. Dividir por dois elimina o último dígito: 111. Subtrair 1 de um número ímpar apaga seu último dígito, um 1: 110. Portanto, cada etapa remove o último dígito ou transforma um 1 final em 0.

Agora conte. Cada 1 no número precisa ser apagado uma vez, o que custa uma subtração por 1. Cada dígito precisa ser removido, o que custa uma divisão por dois por dígito, exceto o primeiro: quando resta apenas 1, a subtração que o apaga já resulta em 0. Portanto, a resposta é length - 1 + ones. Para 14 = 1110, isso é 4 - 1 + 3 = 6.

Java, C, C++, Go, Rust e Swift têm funções integradas para ambas as contagens (uma contagem de zeros à esquerda e uma contagem de bits 1) que compilam para instruções únicas na maioria dos processadores. Nas outras linguagens, escreva n em binário e conte os caracteres, ou leia os dígitos com % 2; isso é um laço de no máximo 31 iterações. Retorne 0 primeiro para n = 0: esse valor não tem nenhum bit 1 para servir de base à fórmula.

Algoritmo

Se n == 0, retorne 0.
Encontre length, o número de dígitos binários de n.
Encontre ones, o número de bits 1.
Retorne length - 1 + ones.

def numberOfSteps(n):
    if n == 0:
        return 0
    # Every bit below the leading one costs a halving,
    # and every 1 bit costs a subtraction.
    return n.bit_length() - 1 + bin(n).count("1")

Armadilhas e casos extremos

A regra tem duas linhas. Os erros estão nos casos-limite e no erro de uma unidade na fórmula.

Esquecer n = 0 na fórmula dos bits. Sem dígitos e sem 1s, length - 1 + ones resulta em -1, e uma contagem de zeros à esquerda de 0 pode ser indefinida (__builtin_clz(0) em C).
Contar uma divisão pela metade para o dígito inicial. 1 se torna 0 por uma subtração, então 8 = 1000 leva 4 - 1 + 1 = 4 passos, não 5.
Juntar duas etapas em uma. Escrever n = (n-1) / 2 para um número ímpar faz uma subtração e uma divisão pela metade de uma só vez, então é preciso adicionar 2 à contagem, não 1. Caso contrário, 14 resulta em 4 em vez de 6.
Fazer o loop enquanto n > 1. Isso para uma etapa antes do tempo, porque a última etapa transforma 1 em 0. O loop deve continuar até que n seja 0.

Perguntas frequentes4

Qual é a complexidade temporal de reduzir um número a zero?

Executar o processo leva tempo O(log n), porque pelo menos a cada segundo passo o número é reduzido à metade. Para n = 2^31 - 1, são 61 passos. Contar os dígitos binários com instruções de bits integradas é O(1).

Qual é a fórmula para o número de passos?

Para n > 0, a resposta é o comprimento de n em binário, menos um, mais o número de bits 1. Cada bit 1 custa uma subtração, e cada dígito abaixo do 1 inicial custa uma divisão por 2. Para n = 0, a resposta é 0.

Qual número abaixo de 2^31 leva mais etapas?

2^31 - 1, que corresponde a trinta e um algarismos 1 em binário. São necessárias 31 subtrações e 30 divisões pela metade, 61 etapas no total. Nenhum número menor tem tantos dígitos e tantos algarismos 1 ao mesmo tempo.

Por que dividir por dois é o mesmo que deslocar para a direita?

Um número binário é uma soma de potências de dois. Dividir um número par por 2 reduz cada potência em um, o que desloca cada dígito uma posição para a direita e remove o 0 final. É exatamente isso que n >> 1 faz, então você pode escrever a divisão pela metade de qualquer uma das duas maneiras.

Python

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

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

n = 14

Esperado