3
\$\begingroup\$

STDIN: Array of integers

STDOUT: Smallest difference (the difference between the closest two numbers in the array).

Rules: Given an array of positive integers find the difference between the closest two numbers in the array. Performance should be taken into consideration.

Example:

STDIN: [55, 99, 6, 29, 1, 523, 3]

STDOUT: 2 (e.g. 3-1)

Scoring: Although somewhat informal, the shortest, most efficient (performance wise) will win. Creativity will also be taken into consideration.

\$\endgroup\$

19 Answers 19

6
\$\begingroup\$

The R language

23 characters, O(n log n)

min(diff(sort(scan())))

Example:

> min(diff(sort(scan())))
1: 55 99 6
4: 29 1 523 3
8: 
Read 7 items
[1] 2

...The [1] 2 shows the result 2. (the [1] is to keep track of where in the result vector your are since in R all values are vectors - in this case of length 1)

\$\endgroup\$
  • \$\begingroup\$ well done, although not very creative! :p useful functions though. \$\endgroup\$ – Thomas Clayson Dec 8 '11 at 15:03
5
\$\begingroup\$

Mathematica, 23

Min@Differences@Sort@#&
\$\endgroup\$
2
\$\begingroup\$

JavaScript, 127 characters

This is a function that takes the array as a string. It may be O((n-1)²/2+n/2-1/2). I have no idea.

function(s){s=eval(s);a=Math.abs;m=a(s[i=0]-s[j=1]);for(;i<s.length;j=++i)for(;++j<s.length;)m=(v=a(s[i]-s[j]))<m?v:m;return m}
\$\endgroup\$
  • 1
    \$\begingroup\$ it's just O(n^2) time complexity \$\endgroup\$ – ratchet freak Nov 30 '11 at 19:40
  • 2
    \$\begingroup\$ use sort and you can eliminate the inner loop s=eval(s).sort;m=a(s[i=0]-s[1]);for(i=2;i<s.length;i++)m=(v=a(s[i]-s[i-1]))<m?v:m; \$\endgroup\$ – ratchet freak Nov 30 '11 at 19:57
2
\$\begingroup\$

Scala, O(n log n)

Script that reads from STDIN (113 chars)

val s=Console.readLine.split(",").map(_.toInt).sortBy(i=>i)
if(s.size<2)0 else s.tail.zip(s).map(x=>x._1-x._2).min

Function (94 chars)

def m(l:Seq[Int])=if(l.size<2)0 else{val s=l.sortBy(i=>i);s.tail.zip(s).map(x=>x._1-x._2).min}
\$\endgroup\$
2
\$\begingroup\$

J, 28

<./&(}.-}:)@/:~&.(".&stdin)_

Very straightforward J, drawn down by I/O and parsing. For those who don't read J fluently:

  • & and @ compose verbs
  • <. / yields a vector's minimum
  • ( }. - }: ) performs pairwise substraction
  • /: ~ sorts up
  • &. performs dark magic so that the next two are used both in the input and output directions
  • ". parses/presents J data
  • stdin takes care of I/O
  • _ is a dummy argument to stdin
\$\endgroup\$
2
\$\begingroup\$

O(n) space and time

C++ (1644 chars)

Reads from stdin

#include <vector>
#include <iostream>
#include <iterator>
#include <algorithm>

int radix(int const& a, int const& r) {return (a >> (r << 3)) & 0xFF;}

template <int R_> 
int radix(int const& a) {return radix(a, R_);}


template <typename It_, typename Cont_>
void distribution(It_ first, It_ const& last, Cont_& d_vector, int const& r) {
        d_vector.resize(256, 0);
        std::fill(d_vector.begin(), d_vector.end(), 0);
        for(; first != last; ++first)
                d_vector[radix(*first, r)]++;
}

template <typename It_, typename Cont_>
void split(It_ first, It_ const& last, Cont_& d_vector, Cont_& slots, int const& r) {
        int cnt = 0;
        for(int i=0; i<256; cnt += d_vector[i++])
                std::swap(d_vector[i], cnt);

        slots.resize(cnt, 0);
        for(; first != last; ++first)
                slots[d_vector[radix(*first, r)]++] = *first;
}

int main(int argc, char* const argv[]) {
        std::istream_iterator<int> in(std::cin);
        std::istream_iterator<int> end;
        std::vector<int>           numbers;

        /// Read numbers
        std::copy(in, end, std::back_inserter(numbers));

        /// Sanity checks
        if(1 >= numbers.size()) {
                std::cerr << "not enough numbers" << std::endl;
                return -1;
        }

        /// Sort the numbers 4 times using different radix
        std::vector<int> d_vector(256, 0);
        std::vector<int> slots;
        for(int r=0; r<4; ++r) {
                distribution(numbers.begin(), numbers.end(), d_vector, r);
                split(numbers.begin(), numbers.end(), d_vector, slots, r);
                numbers.swap(slots);
        }

        /// Compute the min difference
        int prev = numbers[1];
        int min  = prev-numbers[0];
        for(std::size_t i=2; i<numbers.size(); ++i) {
                min = std::min(min, numbers[i]-prev);
        }
        std::cout << min << std::endl;
        return 0;
}
\$\endgroup\$
  • \$\begingroup\$ +1 for the radix sort... although, technically, if we're allowed to assume a maximum value for the inputs, I can use the pigeonhole principle to make any of the given solution run in O(1) time and space. (Read up to M inputs, where M is the maximum input value. If there are more inputs, ignore them and output 0; otherwise use the original code, which now runs in bounded time and space since the input length is bounded.) \$\endgroup\$ – Ilmari Karonen Dec 4 '11 at 14:53
  • \$\begingroup\$ I get the impression that radix sort is best able to beat quicksort when there are duplicate values in the input. The interesting thing is that this golf challenge allows us to immediately exit with 0 (zero difference) if there is a duplicate. Hence, I think that populating an std::set is a reasonable algorithm. It mightn't be very fast, but it's worst-case performance is reasonable. Extra: Don't forget that the number of keys in radix sort will need to be of the order log n anyway (assuming no duplicates in the input), and hence it won't be significantly faster than quicksort. Am I right? \$\endgroup\$ – Aaron McDaid Dec 4 '11 at 23:27
  • \$\begingroup\$ I like this, although you could have golfed it somewhat. :p \$\endgroup\$ – Thomas Clayson Dec 8 '11 at 15:02
2
\$\begingroup\$

APL, 16/18 characters

x←⎕⋄⌊/2-/(x[⍒x])

Or with explicit output:

x←⎕⋄⎕←⌊/2-/(x[⍒x])

Example:

      x←⎕⋄⌊/2-/(x[⍒x])
⎕:
      55 9 6 29 1 523 3
2

Explanation:

  • First expression:
    • x←⎕: Get the input array ( ) and assign it ( ) to x.
  • : Expression separator.
  • Second expression, right to left:
    • (x[⍒x]): Sort the input. ⍒x returns the set of indices needed to sort x in descending order, which is used to index x ( x[...] ).
    • 2-/: Splits ( / ) the input array into pairs ( 2 ) and finds the difference ( - ) between each pair.
    • ⌊/: Reduce ( / ) the array using the floor function ( ).

I used Dyalog APL for this.

\$\endgroup\$
  • \$\begingroup\$ you can shorten by two characters ⌊/2-/(x[⍒x←⎕]) \$\endgroup\$ – protist Nov 23 '13 at 17:13
  • \$\begingroup\$ actually by 4 ⌊/2-/x[⍒x←⎕] \$\endgroup\$ – protist Nov 23 '13 at 17:14
2
\$\begingroup\$

K, 15

......

{min@1_-':x@<x}
\$\endgroup\$
2
\$\begingroup\$

APL 14

(original...21 chars)

{⌊/|{(0≠⍵)/⍵},⍵∘.-⍵}⎕

(edit new shorter...15 chars)

{⌊/|0~⍨,⍵∘.-⍵}⎕

(edit again...14 chars)

⌊/|0~⍨,y∘.-y←⎕

assuming no two numbers are the same

⍝ y←⎕     bring in input
⍝ y∘.-y   create subtraction table of array y against array y
⍝ 0~⍨     remove zeros (from same element against itself
⍝                       on diagonal)
⍝ |       absolute value
⍝ ⌊/      reduce with minimum
\$\endgroup\$
1
\$\begingroup\$

D (124 chars) O(n log n) time complexity

void main(){int[]a;int b;while(readf("%d ",&b))a~=b;b=~0>>>1;sort!(d,c){d-=c;c=d<0?-d:d;b=b<c?b:c;return d;}(a);writeln(b);}

using the comparator to keep a running min while sorting

\$\endgroup\$
1
\$\begingroup\$

Haskell, 71 characters, O(n log n)

import List;f x=zipWith(-)(tail x)x
main=readLn>>=print.minimum.f.sort
\$\endgroup\$
1
\$\begingroup\$

Python 2.6, 56 48 characters, O(n log n)

New version utilizing min, diff, and sort from numpy. Inspired by Tommy's answer.

from numpy import*
print min(diff(sort(input()))

Original version. Inspired by Zachary Vance's answer.

a=sorted(input())
print min(y-x for x,y in zip(a,a[1:]))
\$\endgroup\$
1
\$\begingroup\$

C# 180 Characters

using System;using System.Linq;class P{static void Main(int[]a){Action<int[]> b=Array.Sort;b(a);a=a.Select((c,d)=>(a.Length>d+1?a[d+1]-c:-1)).ToArray();b(a);Console.Write(a[1]);}}

Readable:

using System;
using System.Linq;
class P
{
    static void Main(int[]a)
    {
        Action<int[]> b = Array.Sort;
        b(a);
        a = a.Select((c, d) => (a.Length > d + 1 ? a[d + 1] - c : -1)).ToArray();
        b(a);
        Console.Write(a[1]);
    }
}
\$\endgroup\$
1
\$\begingroup\$

Java

public static int minDifference(int[] A) {
    Arrays.sort(A);
    if (A.length > 1) {
        int d = Math.abs(A[0] - A[1]);
        for (int i = 0; i <= A.length; i++) {
            if (i + 1 < A.length) {
                int t = Math.abs(A[i] - A[i + 1]);
                if (t < d) d = t;
            }
        }
        return d;
    }
    return -1;
}

-1 is returned when an array is too short

\$\endgroup\$
1
\$\begingroup\$

Mathematica 39

Sort standard input,subtract each element n from each element n+1, take the absolute value of those differences, and find the minimum of those.

Min[Abs[RotateLeft@# - #] &[Sort@Input[]]]
\$\endgroup\$
0
\$\begingroup\$

Perl, 49 characters, O(n log n)

say+(sort{$a-$b}map$a*1-($a=$_),sort{$b-$a}<>)[1]

The input should be on separate lines; the output is printed after input ends. (I can also make it parse comma-separated input on one line by using the -naF, command line switches and replacing <> with @F.) The say command is available since Perl 5.10.0 with the -E switch or with use 5.010; per meta its use is allowed at no extra cost.

This uses the same sort-and-diff trick as almost everyone else, with a slight twist to deal with the fact that Perl has no built-in diff command. It first sorts the input in descending order, substracts each number from the previous one in the list and re-sorts the result in ascending order. This leaves one negative value (zero minus the largest input) in front of the list, so the code actually outputs the second smallest value. Of course, this only works as long as the input contains at least one positive number, but fortunately the spec says that all input values must be positive.

(Also, the latest version plays silly tricks with expression evaluation order to shave off a few more chars: apparently $a-($a=$_) always evaluates to 0, but $a*1-($a=$_) ends up saving the previous value of $a on stack before changing it, avoiding the need to store it in a separate variable. With Perl, there ain't no such thing as "undefined behavior"... :)

\$\endgroup\$
0
\$\begingroup\$

J, 10 chars

<./2-/\\:~

It doesn't include explicit input/output, but appending a list to the end like <./2-/\\:~1,2,3 or <./2-/\\:~1 2 3 works as one would expect. I'm not too familiar with J's explicit I/O, unfortunately.

Explanatory refactoring:

sort_down =: \:~
pair_sub =: 2&(-/\)
min =: <./
min pair_sub sort_down 1 2 3

pair_sub is slightly altered, since J has some rules for precedence and verb composition that makes pair_sub =: 2-/\ give an error and pair_sub =: 2&-/\ give a different output when used in the sentence min pair_sub sort_down 1 2 3 as compared to <./2-/\\:~ 1 2 3.

\$\endgroup\$
  • \$\begingroup\$ I usually use ".1!:1[1 for taking a single line of input. \$\endgroup\$ – Gareth Nov 12 '13 at 19:29
0
\$\begingroup\$

Java O(n)

public int minimumDifference(int[] arr) {
    int minimum = 0;

    if (null != arr) {
        int length = arr.length;
        if (length == 1) {
            minimum = arr[0];
        }
        if (length == 2) {
            minimum = Math.abs(arr[0] - arr[1]);
        } else if (length > 2) {
            int minimumSoFar = arr[0];
            int secondMinimumSoFar = arr[0];
            for (int i = 0; i < length; i++) {
                if (arr[i] < minimumSoFar) {
                    minimumSoFar = arr[i];
                }
                if (arr[i] > minimumSoFar && arr[i] < secondMinimumSoFar) {
                    secondMinimumSoFar = arr[i];
                }
            }
            minimum = secondMinimumSoFar - minimumSoFar ;
        }
    }
    return minimum;
}
\$\endgroup\$
-1
\$\begingroup\$

Python 3.1.3, 77 chars

a=sorted(eval(input()))
print(min([abs(x-y)for x,y in zip(a[::2],a[1::2])]))
\$\endgroup\$
  • \$\begingroup\$ Can't you replace abs(x-y) with y-x? \$\endgroup\$ – Keith Randall Nov 30 '11 at 18:12
  • 1
    \$\begingroup\$ Looks like this would give an incorrect answer with input of [1,3,4,6] because you are striding by 2, which will pair the first with the second items, then the third with the fourth, but does not consider the pair of the second and the third. \$\endgroup\$ – Steven Rumbalski Nov 30 '11 at 21:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.