Codingame Solution: Horse-racing Duals

Original Problem

Casablanca’s hippodrome is organizing a new type of horse racing: duals. During a dual, only two horses will participate in the race. In order for the race to be interesting, it is necessary to try to select two horses with similar strength.

Write a program which, using a given number of strengths, identifies the two closest strengths and shows their difference with an integer (≥ 0).

Game Input

Input

Line 1: Number N of horses

The N following lines: the strength P_i of each horse. P_i is an integer.

Output

The difference D between the two closest strengths. D is an integer greater than or equal to 0.

Constraints

1 < N < 100000
0 < P_i ≤ 10000000

Bash Solution

#!/bin/bash

arr=()
read n

for ((i=0 ; i < n ; i++ )); do
    read arr[i]
done

arr=($(printf '%s\n' "${arr[@]}" | sort -g))

diff=0
min_diff=$(( ${arr[1]} - ${arr[0]} ))

for (( i=2 ; i < n ; i++ )); do
   diff=$(( ${arr[$i - 1]} - ${arr[$i]} ))
   if [[ $diff -lt 0 ]]; then
      diff=$((-$diff))
   fi

   if [[ $diff -lt $min_diff ]]; then
      min_diff=$diff
   fi
done

echo $min_diff

« Back to problem overview