The aim of this puzzle is to find the minimum difference between 2 values a list. The difficulty lies in the length of the list, and the short time to do it. A "simple" solution is to first sort all the values efficiently enough, then compare all the differences between consecutive values.

To sort the powers, you could use your own sorting function instead of the standard C function qsort.

#include <stdlib.h> #include <stdio.h> #include <limits.h> /* compares the two integers pointed by e1 and e2, returns -1 / 0 / 1, if e1 < / = / > e2 */ int comp (const void * e1, const void * e2) { int f = *((int*)e1); int s = *((int*)e2); if (f > s) return 1; if (f < s) return -1; return 0; } int main(int argc, char** argv) { int N; scanf("%d\n", &N); int horses[N]; for (int i = 0; i < N; i++) scanf("%d\n", horses+i); // Sorts the powers qsort(horses, N, sizeof(int), comp); int min = INT_MAX; int diff; for (int i = 0; i < N-1; i++) { diff = horses[i+1]-horses[i]; if (diff < min) min = diff; } printf("%d\n", min); return EXIT_SUCCESS; }

Instead of reading all the powers then sorting them, you can also insert them in order in a sorted data structure, as I did in Java.

import java.util.*; class Solution { public static void main(String args[]) { Scanner in = new Scanner(System.in); int N = in.nextInt(); // TreeSet is one of Java's sorted data structure TreeSet<Integer> horses = new TreeSet<Integer>(); for (int i = 0; i < N; i++) horses.add(in.nextInt()); Iterator<Integer> it = horses.iterator(); int curr, prev = it.next(); int min = Integer.MAX_VALUE; while (it.hasNext()) { curr = it.next(); if (curr-prev < min) min = curr-prev; prev = curr; } System.out.println(min); } }

Same algorithm as in Java, using bisect to insert a value in a sorted array (by the bisection method).

import bisect, sys N = int(input()) horses = [] mini, diff = sys.maxsize, None for i in range(N): bisect.insort(horses, int(input())) for i in range(N-1): diff = horses[i+1] - horses[i] if diff < mini: mini = diff print(mini)

I also did this one in Bash to unlock the third achievement. The tricky part is to sort the array containing the powers, but it becomes very easy if you're used to sort the lines of a file.

#!/bin/bash read N # reads all power values and store them in an array for (( i=0; i<N; i++ )) do read p power[$i]=$p done # sorts the array power=($(for p in ${power[@]}; do echo $p; done | sort -n)) # at this point, power contains all the power sorted by increading order # the result expected is the smallest difference between 2 consecutive values min=9999999 for (( i=0; i<${#power[@]}-1; i++ )) do current=${power[$i]} next=${power[$i+1]} diff=$(( next - current)) if [ $diff -lt $min ] then min=$diff fi done echo $min