Steps to Reduce a Number to Zero

Q: Qual é a complexidade de tempo para 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 pela metade: 61 passos para n = 2^31 - 1 . Contar os dígitos binários com instruções de bits integradas é O(1) .

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

2^31 - 1 , que são trinta e um algarismos 1 em binário. Ele precisa de 31 subtrações e 30 divisões por 2, 61 etapas no total. Nenhum número menor tem tantos algarismos e tantos 1s ao mesmo tempo.

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

+10

Comece com um inteiro não negativo n e repita uma regra até chegar 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 segue 14 → 7 → 6 → 3 → 2 → 1 → 0: três divisões pela metade e três subtrações, 6 etapas.

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 algarismos 1. Os seis algarismos 1 custam seis subtrações, e os seis dígitos abaixo do 1 inicial custam seis divisões por 2: 12 passos.

Para ir além

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

Dicas

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

0 de 3 abertas

Solução

No sistema binário, dividir por dois elimina o último dígito, e subtrair 1 de um número ímpar transforma seu último 1 em 0. Portanto, para n > 0, a resposta é o número de dígitos binários mais o número de 1s, menos um. Executar a regra diretamente também é rápido: no máximo 61 etapas.

Execute o processo

Intuição

Execute a regra e conte as etapas. Para 14, o loop visita 7, 6, 3, 2, 1 e 0: seis etapas.

Uma subtração sempre torna um número ímpar 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. Com uma subtração antes de cada divisão pela metade e uma no final, o loop é executado no máximo 61 vezes. Para n = 0, o loop nunca é executado 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

Cada etapa remove o último dígito binário ou transforma um 1 final em 0. 14 é 1110: dividir por 2 resulta em 111, e subtrair a partir de 111 resulta em 110. Cada 1 precisa ser apagado uma vez, o que custa uma subtração por 1. Cada dígito precisa ser removido, com uma divisão por 2 para cada um, exceto o dígito um inicial: quando resta apenas 1, a subtração já resulta em 0. Portanto, a resposta é length - 1 + ones, e para 14 isso é 4 - 1 + 3 = 6.

Java, C, C++, Go, Rust e Swift têm recursos integrados para contar ambas as coisas (zeros à esquerda e bits definidos), que compilam para instruções únicas na maioria dos processadores. Outras linguagens leem os dígitos com % 2 em um loop de no máximo 31 iterações. Trate n = 0 primeiro: não há nenhum bit 1 para servir de base para a 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

Esquecer n = 0 na fórmula dos bits. length - 1 + ones resulta em -1, e uma contagem de zeros à esquerda igual a 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 meio de uma subtração, então 8 = 1000 leva 4 - 1 + 1 = 4 passos, não 5.
Escrever n = (n-1) / 2 para um número ímpar e contar um passo. Essa linha realiza dois passos, então 14 resulta em 4, em vez de 6.
Repetir o laço enquanto n > 1. Isso para antes do último passo, que transforma 1 em 0.

Perguntas frequentes3

Qual é a complexidade de tempo para 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 pela metade: 61 passos para n = 2^31 - 1. Contar os dígitos binários com instruções de bits integradas é O(1).

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

2^31 - 1, que são trinta e um algarismos 1 em binário. Ele precisa de 31 subtrações e 30 divisões por 2, 61 etapas no total. Nenhum número menor tem tantos algarismos e tantos 1s ao mesmo tempo.

Por que dividir por dois é o mesmo que fazer um deslocamento 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, deslocando cada dígito uma posição para a direita e removendo o 0 final. É isso que n >> 1 faz, então você pode escrever a divisão pela metade de qualquer uma das duas formas.

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

Teste #1

Teste #2

Teste #3

Argumento

n = 14

Saída Esperada