The Goal
In this exercise, you have to analyze records of temperature to find the closest to zero.
Rules
Game 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
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.