Temperatures – solution CodinGame en C
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
- 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.
- 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.
- 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.
- 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).
- Afficher le résultatÀ la fin de la boucle, la variable contient la réponse. On l'affiche telle quelle, sans espace superflu.
Complexité
O(n)O(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;
}
Temperatures – Java
Appelle Scanner.nextInt() N fois et part de Integer.MAX_VALUE. C'est sans risque car le cas N == 0 est traité avant la boucle : la sentinelle ne peut jamais être affichée.
import java.util.*;
import java.math.*;
class Solution {
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
if (N == 0)
System.out.println("0");
else {
int T;
int min = Integer.MAX_VALUE;
/* Search the temperature of minimum absolute valueReads
Note a subtilty of the exercice : a temperature T>0 is prefered over -T */
for (int i = 0; i < N; i++) {
T = in.nextInt();
if (Math.abs(T) < Math.abs(min) || (T == -min && T > 0))
min = T;
}
System.out.println(min);
}
}
}
Temperatures – Python 3
Utilise None pour signifier « pas encore de valeur » plutôt qu'un grand nombre arbitraire, ce qui rend la condition plus lisible.
# N can be 0: in that case the second line is empty and the expected answer is 0.
N = int(input())
if N == 0:
print("0")
else:
# None means "nothing seen yet", so the first reading always becomes the current best.
# (Naming it min shadows the built-in min(), harmless here but best avoided in bigger programs.)
min = None
# All readings sit on one line, separated by spaces.
for T in map(int, input().split()):
# Replace the best value if T is strictly closer to 0,
# or if T is the positive twin of the current best (e.g. 5 beats -5).
if (min == None) or (abs(T) < abs(min)) or ((T == -min) and (T > 0)):
min = T
print(min)
Erreurs fréquentes
- Oublier N = 0Le test sans température attend 0. Un code qui part de INT_MAX ou de 5527 sans gérer ce cas affiche la sentinelle, ou plante en lisant une ligne vide.
- Mauvais départageAvec « -5 5 » comme avec « 5 -5 », la réponse est 5. Une simple comparaison stricte < garde la première valeur rencontrée et échoue donc sur l'un des deux ordres.
- Initialiser la meilleure valeur à 0Cela paraît naturel, mais 0 est déjà la réponse parfaite : plus rien ne la remplace. Il faut partir de la première valeur lue ou d'un marqueur « aucune valeur ».
- Comparer les valeurs brutesPrendre le minimum ou le maximum des nombres eux-mêmes renvoie -273 ou 5526, pas la valeur la plus proche de zéro. On compare toujours abs(T).
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.