Coding Solution

Temperatures – solution CodinGame en C

Facilelinear searchabsolute valuetie-breakingedge casesMis à jour le
Réponse courte

On parcourt les températures une seule fois en gardant celle dont la valeur absolue est la plus petite ; en cas d'égalité (par exemple -5 et 5), on garde la valeur positive. Si la liste est vide (N = 0), on affiche 0. C'est une recherche linéaire en O(n), sans mémoire supplémentaire.

L'énoncé

Le programme reçoit un entier N puis une ligne contenant N températures entières comprises entre -273 et 5526. Il doit afficher celle qui est la plus proche de zéro.

Deux cas font échouer la plupart des premières tentatives : quand une valeur négative et une valeur positive sont à la même distance de zéro, c'est la positive qu'il faut renvoyer, et quand N vaut 0, la ligne est vide et la réponse attendue est 0.

La démarche, étape par étape

  1. Traiter d'abord le cas videSi N vaut 0, il n'y a rien à comparer : on affiche 0 et on s'arrête. Le faire dès le début évite de lire une ligne vide ou d'afficher par erreur une valeur sentinelle comme INT_MAX.
  2. Un seul parcoursOn lit les valeurs dans l'ordre en conservant une seule variable « meilleure valeur ». Inutile de stocker ou de trier le tableau : chaque température est comparée une fois puis oubliée.
  3. Comparer les valeurs absoluesUne valeur T remplace la meilleure B si |T| < |B|. Passer par la valeur absolue transforme « le plus proche de zéro » en simple recherche de minimum, c'est tout le cœur de l'exercice.
  4. Départager vers le positifSi |T| == |B|, les deux nombres sont égaux ou opposés. On remplace B seulement si T est positif, c'est-à-dire T == -B et T > 0. Autre façon de le dire : en cas d'égalité, on garde max(T, B).
  5. Afficher le résultatÀ la fin de la boucle, la variable contient la réponse. On l'affiche telle quelle, sans espace superflu.

Complexité

TempsO(n)
MémoireO(1)

Chaque température est examinée une seule fois avec une comparaison en temps constant, et on ne garde que la meilleure valeur. Un tri marcherait aussi, mais coûterait O(n log n) pour rien.

Code de la solution

Temperatures – C

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n;
    scanf("%d", &n);
    int best = 0; /* stays 0 when there is no reading */
    for (int i = 0; i < n; i++) {
        int t;
        scanf("%d", &t);
        if (i == 0 || abs(t) < abs(best) || (abs(t) == abs(best) && t > best))
            best = t;
    }
    printf("%d\n", best);
    return 0;
}

Erreurs fréquentes

Pour aller plus loin

La règle d'égalité peut s'intégrer dans un seul critère de tri : la clé (|T|, -T). La plus petite paire selon cette clé est la réponse, donc en Python min(temps, key=lambda t: (abs(t), -t)) règle le problème en une ligne, et en C ou en Java il suffit de comparer ces deux nombres dans l'ordre. Vu sous cet angle, on comprend aussi pourquoi l'ordre de lecture n'a aucune importance : on calcule un minimum pour un ordre total, qui ne dépend pas de l'ordre des éléments. Un bon test maison : « -273 5526 -1 1 -1 » doit donner 1 quelle que soit la permutation de ces cinq valeurs.

Questions fréquentes

Que faut-il afficher quand il n'y a aucune température ?

Il faut afficher 0. Quand N vaut 0, la deuxième ligne est vide et la sortie attendue est simplement 0.

Entre -5 et 5, laquelle choisir ?

La positive, 5. L'énoncé précise qu'à distance égale de zéro, c'est la température positive qui l'emporte.

Faut-il trier les températures ?

Non. Un seul parcours qui conserve la meilleure valeur suffit et reste plus rapide : O(n) au lieu de O(n log n) pour un tri.

Puzzles similaires

★ 5,0 · 16 avis · 928 utilisateurs Ajouter à Chrome