Closest Numbers · Coding Gym

Solutions

Sorting the sequence is the key to solve this challenge.

Here is a C++ Solution based on zip | map | reduce pattern:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


#include <iterator>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <numeric>
using namespace std;

int main()
{
    int N; cin >> N;
    vector<int> v; v.reserve(N);
    copy_n(istream_iterator<int>(cin), N, back_inserter(v));
    sort(begin(v), end(v));
    auto minDiff = inner_product(next(begin(v)), end(v), begin(v), numeric_limits<int>::max(),
                  [](int curr, int nxt){ return min(curr, nxt); },
                  minus<>{}
    );
    equal(begin(v), end(v)-1, begin(v)+1, [=](int l, int r){
       if (abs(r-l) == minDiff)
           cout << l << " " << r << " ";
       return true;
    });
}

Here is a Javascript solution by Simone Busoli:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


function processData(input) {
    const numbers = input.split('\n')[1].split(' ').map(Number).sort((a, b) => a - b)

    let diff = Math.abs(numbers[numbers.length-1] - numbers[0])
    let output = []


    for(let i = 0; i < numbers.length - 1; i++) {
        const newDiff = Math.abs(numbers[i] - numbers[i+1])

        if(newDiff < diff) {
            diff = newDiff
            output = [numbers[i], numbers[i+1]]
        } else if(newDiff === diff) {
            output.push(numbers[i], numbers[i+1])
        }
    }

    console.log(output.join(' '))
}

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

An Haskell solution by Alessandro Pezzato

Sort the list, make a list of pairs of adjacent numbers, calculate differences between them and filter the list, takin only pairs where the difference is equal to the minimum. We use list comprehension and pattern matching to filter and translate pairs to lists of two elements, so they can be concatenated by concat.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


import Data.List (sort)

closestNumbers :: [Int] -> [Int]
closestNumbers xs =
  concat $ [[x, y] | ((x, y), d) <- zip pairs diffs, d == minimum diffs]
  where
    sorted = sort xs
    pairs = zip sorted (tail sorted)
    diffs = (uncurry . flip) (-) <$> pairs

main =
  interact (unwords . fmap show . closestNumbers . fmap read . tail . words)

A C solutyion by Michele Liberi

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43


void mergesort(int *a, int n)
{
  int m, sz, i, l, r, k, *b;
  if (n>1){
    m=n/2,
    mergesort(a, m),
    mergesort(a+m, n-m);
    sz=m*sizeof(int),
    b=malloc(sz);
    memcpy(b,a,sz);
    l=i=0, r=m, k=0;
    while (l<m)
      if (r<n && b[k]>a[r])
        a[i++]=a[r++];
      else
        ++l, a[i++]=b[k++];
    free(b);
  }
}

int main()
{
  int n, i, *A, m, mindif;
  scanf("%d\n", &n);
  A=malloc(n*sizeof(int));
  for (i=0; i<n; ++i)
    scanf("%d",A+i);
  //for (i=0; i<n; ++i)
  //  fprintf(stderr,"A[%d]=%d\n", i, A[i]);
  mergesort(A,n);
  mindif=A[1]-A[0];
  for (i=0; i<n-1; ++i){
    m=A[i+1]-A[i];
    if (m<mindif)
      mindif=m;
  }
  //printf("mindif=%d\n", mindif);
  for (i=0; i<n-1; ++i)
    if (A[i+1]-A[i]==mindif)
      printf("%d %d ", A[i], A[i+1]);
  printf("\n");
  return 0;
}

A Swift solution by Pietro Basso

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


func closestNumbers(arr: [Int]) -> [Int] {
    let array = arr.sorted()
    let couples = zip(array, array.dropFirst())
    var result = [Int]()
    var currentMin = 10000000
    for (lhs, rhs) in couples {
        let min = abs(lhs - rhs)
        if min < currentMin {
            currentMin = min
            result = [lhs, rhs]
        } else if min == currentMin {
            result.append(contentsOf: [lhs, rhs])
        }
    }
    return result
}

pattern sort