HackerRank ‘Closest Numbers’ Solution

H
Short Problem Definition:

Given a list of unsorted integers, A={a1,a2,…,aN}, can you find the pair of elements that have the smallest absolute difference between them? If there are multiple pairs, find them all.

Link

Closest Numbers

Complexity:

time complexity is O(n*log(n)) // sorting

space complexity is O(n)

Execution:

Just sort the array and print the smallest difference.

Solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#!/usr/bin/py
from sys import maxint
 
def closest(a):
    a.sort()
    smallest_difference = maxint
    smallest_pairs = []
     
    for idx in xrange(len(a)-1):
        diff = a[idx+1] - a[idx]
        if diff < smallest_difference:
            smallest_difference = diff
            smallest_pairs = [(a[idx], a[idx+1])]
        elif diff == smallest_difference:
            smallest_pairs.append((a[idx], a[idx+1]))
     
    for pair in smallest_pairs:
        print pair[0], pair[1],
     
if __name__ == '__main__':
    n = input()
    vec = map(int, raw_input().split())
    closest(vec)

About the author

Add comment

Archives

Categories