Question

Write a program that takes an integer M, and M integer array elements as input. The program needs to find the minimum difference between
two elements in the integer array. The program then needs to print all those pairs of elements that have the minimum difference If more than
one pair has the minimum difference, then the program should print the output in the ascending order. If an element exists in two or more
pairs, then it should be printed two times or more.
For example,
For the input provided as follows to the program:
4
55 44 33 22
The output of the program will be
22 33 33 44 44 55
Explanation: The minimum difference between two elements is 11. Hence the pairs are printed in the ascending order Here 33 and 44 appear
in two different pairs; hence both are printed twice
Review​

Answer 1

Answer:

search

Sign In

Home

Courses

Algorithmskeyboard_arrow_down

Data Structureskeyboard_arrow_down

Languageskeyboard_arrow_down

Interview Cornerkeyboard_arrow_down

GATEkeyboard_arrow_down

CS Subjectskeyboard_arrow_down

Studentkeyboard_arrow_down

Jobskeyboard_arrow_down

GBlog

Puzzles

What's New ?

▲

Find minimum difference between any two elements

Last Updated: 20-06-2018

Given an unsorted array, find the minimum difference between any pair in given array.

Examples :

Input : {1, 5, 3, 19, 18, 25}; Output : 1 Minimum difference is between 18 and 19 Input : {30, 5, 20, 9}; Output : 4 Minimum difference is between 5 and 9 Input : {1, 19, -4, 31, 38, 25, 100}; Output : 5 Minimum difference is between 1 and -4

Recommended: Please solve it on “PRACTICE” first, before moving on to the solution.

Method 1 (Simple: O(n2)

A simple solution is to use two loops.

C/C++

// C++ implementation of simple method to find

// minimum difference between any pair

#include <bits/stdc++.h>

using namespace std;

  

// Returns minimum difference between any pair

int findMinDiff(int arr[], int n)

{

   // Initialize difference as infinite

   int diff = INT_MAX;

  

   // Find the min diff by comparing difference

   // of all possible pairs in given array

   for (int i=0; i<n-1; i++)

      for (int j=i+1; j<n; j++)

          if (abs(arr[i] - arr[j]) < diff)

                diff = abs(arr[i] - arr[j]);

  

   // Return min diff

   return diff;

}

  

// Driver code

int main()

{

   int arr[] = {1, 5, 3, 19, 18, 25};

   int n = sizeof(arr)/sizeof(arr[0]);

   cout << "Minimum difference is " << findMinDiff(arr, n);

   return 0;

}

Java

Python

C#

PHP

Output :Minimum difference is 1

 

Method 2 (Efficient: O(n Log n)

The idea is to use sorting. Below are steps.

1) Sort array in ascending order. This step takes O(n Log n) time.

2) Initialize difference as infinite. This step takes O(1) time.

3) Compare all adjacent pairs in sorted array and keep track of minimum difference. This step takes O(n) time.