# Codingame Solution: Temperatures

Original Problem

## The Goal

In this exercise, you have to analyze records of temperature to find the closest to zero.

Sample temperatures
Here, -1 is the closest to 0.

## Rules

Write a program that prints the temperature closest to 0 among input data. If two numbers are equally close to zero, positive integer has to be considered closest to zero (for instance, if the temperatures are -5 and 5, then display 5).

## Game Input

Your program must read the data from the standard input and write the result on the standard output.
Input

Line 1: N, the number of temperatures to analyze

Line 2: A string with the N temperatures expressed as integers ranging from -273 to 5526

Output
Display 0 (zero) if no temperatures are provided. Otherwise, display the temperature closest to 0.
Constraints
0 ≤ N < 10000

## Solution

When we start reading the temperatures $$t_i$$ with the first iteration, we don't have a current minimum $$m$$, so that the first element will always update the minimum. From now on the minimum will only be set to the current element $$t_i$$ if $$|t_i| < |m|$$. When $$|t_i| = |m|$$ we need to set the minimum to the absolute value $$|t_i|$$. That means we can implement the check like this:

#include <iostream>
#include <sstream>

using namespace std;

int main() {
int N;
cin >> N;
cin.ignore();
string TEMPS;
getline(cin, TEMPS);

istringstream buf(TEMPS);

int t, m = 0;
for (int i = 0; i < N; ++i) {

buf >> t;

if (i == 0 || abs(t) < abs(m)) {
m = t;
} else if (abs(t) == abs(m)) {
m = abs(t);
}
}
cout << m << endl;
return 0;
}

This algorithm works fine, but we call the abs function quite often. We can remove the else-if branch by dissecting all cases for $$|t_i| = |m|$$:

t > 0
m > 0: keep m
m < 0: take t
m = 0: keep m
t < 0
m > 0: keep m
m < 0: keep m
m = 0: keep m
t = 0
m > 0: keep m
m < 0: keep m
m = 0: keep m

That means we can remove the else-if branch and add t == -m && t > 0 or'ed to the first. We can do the same for $$|t| < |m|$$:

t > 0
m > 0
t < m
m < 0
t < -m
m = 0
false

t < 0
m > 0
-t < m
m < 0
-t < -m
m = 0
false

t = 0
m > 0
t < m
m < 0
t < -m
m = 0
false

=>

t > 0, m > 0, t < m
t > 0, m < 0, t < -m
t < 0, m > 0,-t < m
t < 0, m < 0,-t < -m
t = 0, m > 0, t < m
t = 0, m < 0, t < -m

=>

t > 0, m > t
t > 0, m < -t
t < 0, m > -t
t < 0, m < t
t = 0, m > t
t = 0, m < t

=>

t >= 0, m > t
t < =0, m < t
t > 0, m < -t
t < 0, m > -t

t > 0, t = -m # from first equation

=>

t >= 0, m > t
t <= 0, m < t
t > 0, m <= -t
t < 0, m > -t

Stating the improved algorithm again:

#include <iostream>
#include <sstream>

using namespace std;

int main() {
int N;
cin >> N;
cin.ignore();
string TEMPS;

if (N == 0) {
cout << 0 << endl;
return 0;
}

getline(cin, TEMPS);

istringstream buf(TEMPS);

int t, m;
buf >> m;
for (int i = 1; i < N; ++i) {

buf >> t;

if (t >= 0 && m > t || t <= 0 && m < t || t > 0 && m <= -t || t < 0 && m > -t) {
m = t;
}
}
cout << m << endl;
return 0;
}

Well, the original code was much more readable and is thus of more practical value, but it was nice to see how far we can go with the optimization.

« Back to problem overview

All images are copyright to Codingame