puzzle contents
Contents
raw puzzle

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.

All images are copyright to Codingame