Tutte le sfide
Facile 0 risolte 0% di accettazione

Radice quadrata intera

Trova il più grande numero intero il cui quadrato non supera n, senza usare la funzione radice quadrata.

Cosa imparerai

  • Cercare una risposta in un intervallo con la ricerca binaria
  • Confrontare r × r con n senza andare in overflow
  • Evitare gli errori di arrotondamento della virgola mobile

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

Esempio 1
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.

Esempio 2
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.

La migliore soluzione superata di ogni programmatore. Le più veloci, leggere e meglio valutate stanno in alto.

Ancora nessuna soluzione superata. Risolvila e prendi il primo posto.

Impara dagli altri

Soluzioni della community

Nessuna soluzione pubblicata. Risolvi questa sfida per condividere la prima.