Problem Statement:
Given an unsorted array, list all the pairs with the least difference.
Example:
Input:
{5, 4, 3, 2, 1}
Output:
{1, 2}, {2, 3}, {3, 4}, {4, 5}.
Solution Explanation:
Step 1: Sort the array.
Step 2: Find the least difference.
Step 3: Find all the pairs with that least difference.
First, we take a for loop to find out the least difference. According to the below array, it is 1.
{5, 4, 3, 2, 1}
After that we do the following steps:
Pass 1: Least_difference = 1; Print {1, 2}
Pass 2: Least_difference = 1; Print {2, 3}
Pass 3: Least_difference = 1; Print {3, 4}
Pass 4: Least_difference = 1; Print {4, 5}
The solution in C:
#include<stdio.h> #include <limits.h> // for INT_MAX void print_array(int array[], int length) { int index = 0; printf("The sorted array is \n"); for(index = 0 ; index < length ; index++) { printf("%d\n",array[index] ); } } void swap (int *num_1, int *num_2) { int temp = *num_1; *num_1 = *num_2; *num_2 = temp; } void bubble_sort (int array[], int length) { int outer_loop = 0; int inner_loop = 0; for(outer_loop = 0; outer_loop < length - 1; outer_loop ++) { for(inner_loop = 0; inner_loop < length - outer_loop - 1 ; inner_loop ++) { if(array [inner_loop] > array[inner_loop+1]) { swap(&array[inner_loop], &array [inner_loop+1]); } } } } void getLeastDifferencePairs(int arr[], int lenght) { int least_diff = INT_MAX; int itr = 0; int element_1 = 0; int element_2 = 0; for ( itr = 1; itr < lenght; itr++) { if (arr[itr] - arr[itr - 1] < least_diff) { least_diff = arr[itr] - arr[itr - 1]; } } for (itr = 1; itr < lenght; ++itr) // start with 1, if not the result will be negative { if(arr[itr] - arr[itr - 1] == least_diff) { printf("The least diff = %d, element 1 = %d, element 2 = %d\n", least_diff, arr[itr], arr[itr-1] ); } } } int main() { int arr [100] = {5, 4, 3, 2, 1}; int length = 5; bubble_sort(arr, length); getLeastDifferencePairs(arr, length); }
Output:
The least diff = 1, element 1 = 2, element 2 = 1 The least diff = 1, element 1 = 3, element 2 = 2 The least diff = 1, element 1 = 4, element 2 = 3 The least diff = 1, element 1 = 5, element 2 = 4
Devendra Kumar
Fristly , sort the array with n(log(n)) complexity…
Sorting using heap sort , or counting sort (complexity (n)…….
Now find least difference using one loop..
Now print all pairs using one loop which has least difference…..
Total complexity : n(log n) or
: o(n) (counting sort)