Problema
La radice quadrata intera di n è la radice quadrata arrotondata per difetto, cioè il più grande intero r tale che r × r ≤ n. Le radici quadrate di libreria lavorano con numeri in virgola mobile e, con input grandi, possono sbagliare di uno: calcolala quindi usando solo interi, per esempio con una ricerca binaria sulle possibili risposte.
Implementa integer_square_root(n).
Input
n: un intero non negativo.
Output
Restituisci il più grande intero r tale che r × r ≤ n.
Vincoli
0 ≤ n ≤ 10^18
Esempi
Input:
n = 50
Output atteso:
expected = 7
Input:
long long n = 50;
Output atteso:
long long expected = 7;
Input:
long n = 50;
Output atteso:
long expected = 7;
Spiegazione
7 × 7 = 49 ≤ 50, mentre 8 × 8 = 64 > 50, quindi la risposta è 7.
Input:
n = 144
Output atteso:
expected = 12
Input:
long long n = 144;
Output atteso:
long long expected = 12;
Input:
long n = 144;
Output atteso:
long expected = 12;
Spiegazione
144 è esattamente 12 × 12, quindi la risposta è 12.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
La risposta sta tra 0 e n, e r × r cresce al crescere di r, quindi puoi dimezzare l'intervallo a ogni passo.
Suggerimento 2
Per n grandi, r × r può andare in overflow; confronta invece r con n / r, oppure limita l'estremo superiore.
Suggerimento 3
Controlla a mano input piccoli come 0, 1 e 3.
Complessità attesa
tempo O(log n), spazio aggiuntivo O(1)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.