Steps to Reduce a Number to Zero

Q: Qual è la complessità temporale per ridurre un numero a zero?

L'esecuzione del processo richiede un tempo O(log n) , perché almeno ogni secondo passaggio dimezza il numero. Per n = 2^31 - 1 sono 61 passaggi. Contare le cifre binarie con istruzioni sui bit integrate è O(1) .

Q: Qual è la formula per il numero di passaggi?

Per n > 0 , la risposta è la lunghezza di n in binario, meno uno, più il numero di bit a 1. Ogni bit a 1 richiede una sottrazione e ogni cifra dopo l’1 iniziale richiede un dimezzamento. Per n = 0 la risposta è 0 .

Q: Quale numero minore di 2^31 richiede più passaggi?

2^31 - 1 , che in binario è composto da trentuno 1. Richiede 31 sottrazioni e 30 divisioni per due, 61 passaggi in totale. Nessun numero più piccolo ha così tante cifre e così tanti 1 contemporaneamente.

PrincipianteManipolazione dei bit Matematica e simulazione

+10

Parti da un intero non negativo n e ripeti una regola finché non raggiunge 0: se il numero è pari, dividilo per 2; se è dispari, sottrai 1. Ogni applicazione della regola è un passaggio. Restituisci il numero di passaggi necessari.

Funzione

numberOfSteps(n: integer) → integer

ninteger: il numero iniziale
Restituisceinteger: il numero di passaggi finché il numero non raggiunge 0

Vincoli

0 ≤ n ≤ 2³¹ - 1

Esempi

Input: n = 14
Output: 6
Spiegazione: Il numero procede 14 → 7 → 6 → 3 → 2 → 1 → 0: tre divisioni per due e tre sottrazioni, 6 passaggi.

Input: n = 8
Output: 4
Spiegazione: 8 → 4 → 2 → 1 → 0. Una potenza di due si dimezza tre volte e ha bisogno di una sottrazione alla fine, 4 passaggi.

Input: n = 123
Output: 12
Spiegazione: 123 è 1111011 in binario: sette cifre e sei 1. I sei 1 costano sei sottrazioni e le sei cifre sotto l'uno iniziale costano sei divisioni per due, 12 passaggi.

+12 test nascosti all’invio

Per approfondire

Supponiamo che un numero dispari possa anche aumentare di 1 invece di diminuire. Qual è il numero minimo di passaggi per arrivare a 0 e quale scelta è corretta per 15?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Eseguire la regola è già veloce: ogni dimezzamento divide il numero a metà, quindi persino 2^31 - 1 richiede solo 61 passaggi. La parte interessante è osservare cosa fa la regola alle cifre binarie. Dimezzare elimina l’ultima cifra e sottrarre 1 da un numero dispari trasforma il suo ultimo 1 in uno 0. Quindi la risposta è il numero di cifre più il numero di 1, meno uno.

Esegui il processo

Intuizione

Fai ciò che dice l’istruzione. Finché n è maggiore di 0, dimezzalo se è pari, sottrai 1 se è dispari e conta il passaggio. Per 14 il ciclo visita 7, 6, 3, 2, 1 e 0: sei passaggi.

Il ciclo è breve perché una sottrazione rende sempre pari un numero dispari, quindi almeno un passaggio ogni due è un dimezzamento. Un numero minore di 2^31 viene dimezzato al massimo 30 volte prima di raggiungere 1 e, con una sottrazione prima di ogni dimezzamento e una alla fine, il ciclo viene eseguito al massimo 61 volte.

L’input 0 non richiede casi speciali: la condizione del ciclo non è soddisfatta fin da subito e la risposta è 0.

Algoritmo

Imposta steps su 0.
Mentre n > 0: se n è pari, imposta n su n / 2, altrimenti su n-1.
Aggiungi 1 a steps ogni volta.
Restituisci steps.

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

Conta le cifre binarie

Intuizione

Osserva il processo in binario. 14 è 1110. Dimezzare elimina l’ultima cifra: 111. Sottrarre 1 da un numero dispari azzera la sua ultima cifra, un 1: 110. Quindi, a ogni passaggio, si elimina l’ultima cifra oppure si trasforma un 1 finale in uno 0.

Ora conta. Ogni 1 nel numero deve essere azzerato una volta, il che richiede una sottrazione per ogni 1. Ogni cifra deve essere rimossa, il che richiede un dimezzamento per ogni cifra, tranne quella iniziale: quando rimane solo 1, la sottrazione che lo azzera produce già 0. Quindi la risposta è length - 1 + ones. Per 14 = 1110 il risultato è 4 - 1 + 3 = 6.

Java, C, C++, Go, Rust e Swift hanno funzioni integrate per entrambi i conteggi (il conteggio degli zeri iniziali e il conteggio dei bit a 1), che sulla maggior parte dei processori vengono compilate in singole istruzioni. Negli altri linguaggi si scrive n in binario e si contano i caratteri, oppure si leggono le cifre con % 2; si tratta di un ciclo di al massimo 31 iterazioni. Restituisci prima 0 per n = 0: non ha bit a 1 a cui ancorare la formula.

Algoritmo

Se n == 0, restituisci 0.
Trova length, il numero di cifre binarie di n.
Trova ones, il numero di bit a 1.
Restituisci 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")

Trappole e casi limite

La regola è di due righe. Gli errori riguardano i casi limite e l'errore di una unità nella formula.

Dimenticare n = 0 nella formula dei bit. Senza cifre e senza 1, length - 1 + ones dà -1, e un conteggio degli zeri iniziali pari a 0 potrebbe essere indefinito (__builtin_clz(0) in C).
Contare una divisione per due per la cifra iniziale. 1 diventa 0 con una sottrazione, quindi 8 = 1000 richiede 4 - 1 + 1 = 4 passaggi, non 5.
Unire due passaggi in uno. Scrivere n = (n-1) / 2 per un numero dispari esegue una sottrazione e una divisione per due contemporaneamente, quindi bisogna aggiungere 2 al conteggio, non 1. Altrimenti 14 risulta pari a 4 invece di 6.
Ripetere il ciclo mentre n > 1. Così ci si ferma un passaggio prima, perché l'ultimo passaggio trasforma 1 in 0. Il ciclo deve continuare finché n è 0.

Domande frequenti4

Qual è la complessità temporale per ridurre un numero a zero?

L'esecuzione del processo richiede un tempo O(log n), perché almeno ogni secondo passaggio dimezza il numero. Per n = 2^31 - 1 sono 61 passaggi. Contare le cifre binarie con istruzioni sui bit integrate è O(1).

Qual è la formula per il numero di passaggi?

Per n > 0, la risposta è la lunghezza di n in binario, meno uno, più il numero di bit a 1. Ogni bit a 1 richiede una sottrazione e ogni cifra dopo l’1 iniziale richiede un dimezzamento. Per n = 0 la risposta è 0.

Quale numero minore di 2^31 richiede più passaggi?

2^31 - 1, che in binario è composto da trentuno 1. Richiede 31 sottrazioni e 30 divisioni per due, 61 passaggi in totale. Nessun numero più piccolo ha così tante cifre e così tanti 1 contemporaneamente.

Perché dimezzare equivale a uno spostamento a destra?

Un numero binario è una somma di potenze di due. Dividere un numero pari per 2 riduce di uno ogni potenza, spostando ogni cifra di una posizione verso destra ed eliminando lo 0 finale. È esattamente ciò che fa n >> 1, quindi puoi scrivere la divisione a metà in entrambi i modi.

Python

def numberOfSteps(n):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

n = 14

Atteso