Sorting is useful as the first step in many different tasks. The most common task is to make finding things easier, but there are other uses as well. In this case, it will make it easier to determine which pair or pairs of elements have the smallest absolute difference between them.
Also, if you want to learn data structures and algorithms that I will suggest you Abdul Bari Sir Data Structures and Algorithm Course. I took this course before my placement season that it helped me a lot to strengthen up my basics. Abdul Sir is on YouTube and you can watch the quality of lectures and how easily he explains each topic.
Example
arr=[5,2,3,4,1]
Sorted,arr’=[1,2,3,4,5] . Several pairs have the minimum difference of 1:[(1,2),(2,3),(3,4),(4,5)} . Return the array [1,2,2,3,3,4,4,5].
Note
As shown in the example, pairs may overlap.
Given a list of unsorted integers, arr , find the pair of elements that have the smallest absolute difference between them. If there are multiple pairs, find them all.
Function Description
Complete the closestNumbers function in the editor below.
closestNumbers has the following parameter(s):
- int arr[n]: an array of integers
Returns
– int[]: an array of integers as described
Input Format
The first line contains a single integer n, the length of arr.
The second line contains n space-separated integers, arr[i].
Constraints
- 2<=n<=200000
- -10^7<=arr[i]<=10^7
- All a[i] are unique in arr.
Output Format
Sample Input 0
10 -20 -3916237 -357920 -3620601 7374819 -7330761 30 6246457 -6461594 266854
Sample Output 0
-20 30
Explanation 0
(30) – (-20) = 50, which is the smallest difference.
Sample Input 1
12 -20 -3916237 -357920 -3620601 7374819 -7330761 30 6246457 -6461594 266854 -520 -470
Sample Output 1
-520 -470 -20 30
Explanation 1
(-470) – (-520) = 30 – (-20) = 50, which is the smallest difference.
Closest Numbers HackerRank Solution in C
/* Smallest difference */
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
static int compare (const void *a, const void *b)
{
return *((int *) a) - *((int *) b);
}
int main (void)
{
int n, *arr, i, min_diff = INT_MAX, min_ind[1024], curr_diff, count = 0;
scanf (" %d", &n);
arr = malloc (sizeof (int) * n);
for (i=0; i<n; i++)
{
scanf (" %d", &arr[i]);
}
qsort (arr, n, sizeof (int), compare);
for (i=0; i<n-1; i++)
{
curr_diff = abs (arr[i+1] - arr[i]);
if (curr_diff < min_diff)
{
min_diff = curr_diff;
count = 0;
min_ind[count++] = i;
}
else if (curr_diff == min_diff)
{
min_ind[count++] = i;
}
}
for (i=0; i<count; i++)
{
printf ("%d %d ", arr[min_ind[i]], arr[min_ind[i]+1]);
}
free (arr);
return 0;
}
Closest Numbers HackerRank Solution in C++
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int cmp(int x,int y)
{
return x<y;
}
int main() {
vector<int> arr,temp;
int i,n,diff,x;
cin>>n;
for(i=0;i<n;i++)
{
cin>>x;
arr.push_back(x);
}
sort(arr.begin(),arr.end(),cmp);
diff=arr[1]-arr[0];
for(i=2;i<n;i++)
if(diff>(arr[i]-arr[i-1]))
{
diff=arr[i]-arr[i-1];
temp.clear();
temp.push_back(arr[i-1]);
temp.push_back(arr[i]);
}
else if(diff==(arr[i]-arr[i-1]))
{
temp.push_back(arr[i-1]);
temp.push_back(arr[i]);
}
for(i=0;i<temp.size();i++)
cout<<temp[i]<<" ";
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
return 0;
}
Closest Numbers HackerRank Solution in Java
import java.util.*;
import java.io.*;
public class Solution {
private static int[] input;
private static void compute(int[] input){
List<Integer> result = new ArrayList<Integer>();
Arrays.sort(input);
int mindist = Integer.MAX_VALUE;
Set<Integer> indexes = new HashSet<Integer>();
int currdist;
for(int i = 0; i < input.length-1; i++){
currdist = input[i+1] - input[i];
if(currdist < mindist){
indexes = new HashSet<Integer>();
indexes.add(i);
mindist = currdist;
}
if(currdist == mindist){
indexes.add(i);
}
}
Iterator<Integer> it = indexes.iterator();
int next;
while(it.hasNext()){
next = it.next();
result.add(input[next]);
result.add(input[next+1]);
}
Collections.sort(result);
for(int k = 0; k < result.size(); k++){
System.out.print(result.get(k)+" ");
}
}
public static void main(String[] args) throws IOException{
int N;
String[] temp;
String line = "";
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
line = br.readLine();
N = Integer.parseInt(line);
line = br.readLine();
temp = line.split(" ");
input = new int[N];
for(int i = 0; i < N; i++){
input[i] = Integer.parseInt(temp[i]);
}
compute(input);
}
}
Closest Numbers HackerRank Solution in Python
# Enter your code here. Read input from STDIN. Print output to STDOUT
def main():
n = input()
arr = sorted(map(int, raw_input().split()))
diff = 10**8
prev = arr.pop(0)
for i in arr:
if i-prev<diff:
ans = [prev,i]
diff = i-prev
elif i-prev==diff:
ans.append(prev)
ans.append(i)
prev = i
ans.sort()
print " ".join(map(str,ans))
if __name__ == '__main__':
main()
Closest Numbers HackerRank Solution in C#
using System;
using System.Collections.Generic;
using System.IO;
class Solution {
static void Main(String[] args) {
int _a_size = Convert.ToInt32(Console.ReadLine());
int[] _a = new int [_a_size];
String move = Console.ReadLine();
String[] move_split = move.Split(' ');
for(int _a_i = 0; _a_i < _a.Length; _a_i++)
_a[_a_i] = Convert.ToInt32(move_split[_a_i]);
Array.Sort(_a);
int minDiff = Int32.MaxValue;
for(int _a_i = 1; _a_i < _a.Length; _a_i++)
minDiff = Math.Min(_a[_a_i] - _a[_a_i-1], minDiff);
for(int _a_i = 1; _a_i < _a.Length; _a_i++) {
if (minDiff == _a[_a_i] - _a[_a_i-1]) {
Console.Write(_a[_a_i-1]);
Console.Write(' ');
Console.Write(_a[_a_i]);
Console.Write(' ');
}
}
}
}
Attempt Closest Numbers Hackerrank Challenge
Link – https://www.hackerrank.com/challenges/closest-numbers/
Next HackerRank Challenge Solution
Link – https://exploringbits.com/the-love-letter-mystery-hackerrank-solution/
Aayush Kumar Gupta is the founder and creator of ExploringBits, a website dedicated to providing useful content for people passionate about Engineering and Technology. Aayush has completed his Bachelor of Technology (Computer Science & Engineering) from 2018-2022. From July 2022, Aayush has been working as a full-time Devops Engineer.
