Problema
La spirale infinita inizia dalla cella in alto a sinistra. Le prime quattro righe e colonne sono mostrate qui sotto. Continua lo stesso schema in strati quadrati crescenti. Le coordinate partono da 1.
1 2 9 10
4 3 8 11
5 6 7 12
16 15 14 13Restituisci il valore di una cella senza costruire l'intera griglia.
Implementa number_spiral(row, column).
Input
row: La riga contata dall'alto, a partire da 1.
column: La colonna contata da sinistra, a partire da 1.
Output
Restituisci il numero in quella posizione.
Vincoli
1 ≤ row, column ≤ 1.000.000.000. Il valore rientra in un intero con segno a 64 bit.
Esempi
Input:
row = 3
column = 2
Output atteso:
expected = 6Input:
long long row = 3;
long long column = 2;
Output atteso:
long long expected = 6;Input:
long row = 3;
long column = 2;
Output atteso:
long expected = 6;Spiegazione
Nella terza riga mostrata, il secondo valore è 6.
Input:
row = 1
column = 4
Output atteso:
expected = 10Input:
long long row = 1;
long long column = 4;
Output atteso:
long long expected = 10;Input:
long row = 1;
long column = 4;
Output atteso:
long expected = 10;Spiegazione
Il quarto strato quadrato inizia da 10 nella riga superiore.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
La spirale è costruita in strati quadrati, quindi una cella appartiene a uno strato determinato dalla coordinata maggiore.
Suggerimento 2
Usa la parità di quello strato per decidere se i valori aumentano lungo una riga o una colonna.
Suggerimento 3
Attenzione a capire se lo strato parte dall'angolo in alto a sinistra o da quello opposto.
Complessità attesa
tempo O(1), spazio aggiuntivo O(1)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.