Tous les défis
Moyen 1 résolu 100.0 % de réussite

Recherche dans une spirale numérique

Trouvez une valeur à partir de la ligne et de la colonne dans une spirale numérique en expansion.

Ce que vous allez apprendre

  • Trouver une formule dans un motif de nombres
  • Découper le problème par couche et par parité
  • Utiliser des entiers 64 bits pour les grandes valeurs

Problème

La spirale infinie commence dans la cellule en haut à gauche. Les quatre premières lignes et colonnes sont illustrées ci-dessous. Continuez le même motif en couches carrées qui s'étendent. Les coordonnées commencent à 1.

 1   2   9  10
 4   3   8  11
 5   6   7  12
16  15  14  13

Retournez la valeur d'une cellule sans construire toute la grille.

Implémentez number_spiral(row, column).

Entrée

row : La ligne comptée depuis le haut, en commençant à 1.

column : La colonne comptée depuis la gauche, en commençant à 1.

Sortie

Retournez le nombre à cette position.

Contraintes

1 ≤ row, column ≤ 1 000 000 000. La valeur tient dans un entier signé 64 bits.

Exemples

Exemple 1
Entrée :
row = 3
column = 2

Sortie attendue :
expected = 6
Entrée :
long long row = 3;
long long column = 2;

Sortie attendue :
long long expected = 6;
Entrée :
long row = 3;
long column = 2;

Sortie attendue :
long expected = 6;

Explication

Dans la troisième ligne affichée, la deuxième valeur est 6.

Exemple 2
Entrée :
row = 1
column = 4

Sortie attendue :
expected = 10
Entrée :
long long row = 1;
long long column = 4;

Sortie attendue :
long long expected = 10;
Entrée :
long row = 1;
long column = 4;

Sortie attendue :
long expected = 10;

Explication

La quatrième couche carrée commence à 10 dans la ligne du haut.

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

La spirale est construite en couches carrées, donc une case appartient à une couche déterminée par la plus grande coordonnée.

Indice 2

Utilise la parité de cette couche pour décider si les valeurs augmentent le long d’une ligne ou d’une colonne.

Indice 3

Fais attention à savoir si la couche part d’abord du coin supérieur gauche ou du coin opposé.

Complexité attendue

temps O(1), espace supplémentaire O(1)

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

# Codeur Langage Temps Mémoire Note de l'IA Solution
1 ННикита Python 986 ms - 5/5 Voir le code

Apprenez des autres

Solutions de la communauté

Attention spoiler : 1 solution complète ci-dessous Essayez d'abord de le résoudre vous-même. Vous pouvez toujours jeter un œil au code des autres développeurs et aux avis IA. Connectez-vous et résolvez le défi pour rejoindre la discussion.