Closest Numbers – HackerRank Solution

In this post, we will solve Closest Numbers HackerRank Solution. This problem (Closest Numbers) is a part of HackerRank Problem Solving series.

Task

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.

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
  • -107 <= arr[i] <= 107
  • All a[i] are unique in arr.

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.

Sample Input 2

4
5 4 3 2

Sample Output 2

2 3 3 4 4 5

Explanation 2

Here, the minimum difference is 1. Valid pairs are (2, 3)(3, 4), and (4, 5).

Solution – Closest Numbers – HackerRank Solution

C++

#include<iostream>
#include<algorithm>
#include<climits>
#include<vector>
using namespace std;

int a[200000];

vector<int> ansv;

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a, a + n);
    int ans = INT_MAX;
    for (int i = 1; i < n; i++)
    {
        if (a[i] - a[i - 1] < ans)
        {
            ansv.clear();
            ans = a[i] - a[i - 1];
            ansv.push_back(a[i - 1]);
            ansv.push_back(a[i]);
        }
        else if (a[i] - a[i - 1] == ans)
        {
            ansv.push_back(a[i - 1]);
            ansv.push_back(a[i]);
        }
    }
    for (int i = 0; i < (int)ansv.size(); i++)
        cout << ansv[i] << " ";
    cout << endl;
    return 0;
}

Python

#!/bin/python3

import sys


def closestNumbers(arr):
    output = []
    arr = sorted(arr)
    nowmin = 10**9
    
    for ind in range(1, len(arr)):
        diff = abs(arr[ind-1] - arr[ind])
        
        if diff < nowmin:
            output = [(arr[ind-1], arr[ind])]
            nowmin = diff
        elif diff == nowmin:
            output.append((arr[ind-1], arr[ind]))
            
    flat_list = [item for sublist in output for item in sublist]
        
    return flat_list
    

if __name__ == "__main__":
    n = int(input().strip())
    arr = list(map(int, input().strip().split(' ')))
    result = closestNumbers(arr)
    print (" ".join(map(str, result)))

Java

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int[] array = new int[n];
        for(int i = 0; i < n; i++)
            array[i] = input.nextInt();
        
        Arrays.sort(array);
        int minAbs = Integer.MAX_VALUE; //Minimum absolute difference
        StringBuilder pairs = new StringBuilder("");
        
        for(int i = 0; i < n-1; i++)
        {
            int absDiff;
            
            if((array[i]<0 && array[i+1]<0)||(array[i]>0 && array[i+1]>0))//both numbers have matching signs
                absDiff = Math.abs(array[i] - array[i+1]); //Absolute difference
            else
                absDiff = Math.abs(array[i]) + Math.abs(array[i+1]); //Absolute difference
            
            if(absDiff < minAbs)//New minAbs
            {
                minAbs = absDiff;
                pairs = new StringBuilder("");//Empty pairs
                pairs.append(array[i]+ " " +array[i+1]+" ");//Add pair
            }
            else if(absDiff == minAbs)//Multiple minAbs
                pairs.append(array[i]+ " " +array[i+1]+" ");//Add pair
        }
        
        System.out.println(pairs);
    }
}

Note: This problem (Closest Numbers) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.

Leave a Comment

Your email address will not be published. Required fields are marked *