Codingame Solution: Temperatures

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.

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.