Problem Explanation:
Given an unsorted array, the output should be the minimum difference between the elements and the elements itself.
Example:
Input:
{6, 10, 5, 42, 43, 1, 2}
output:
The minimum difference between is 1 the elements are 1 and 2.
This can be solved in 2 ways:
Solution 1:
Take a “diff” variable that will hold the least difference and iterate through the array by taking 2 for loops, outer loop and inner loop.
Note:
abs() is used in this program. It will the absolute value of an integer. Absolute value means a +ve value of that integer.
As we are using 2 for loops the efficiency is O(n^2).
Below is the solution in C:
#include<stdio.h> #include <limits.h> // for INT_MAX #include <stdlib.h> // for abs() void getLeastDifference(int arr[], int lenght) { int diff = INT_MAX; //. we set the initial difference as max. int outer_loop = 0; int inner_loop = 0; int element_1 = 0; int element_2 = 0; for ( outer_loop = 0; outer_loop < lenght-1 ; ++outer_loop) { for ( inner_loop = outer_loop +1 ; inner_loop < lenght; ++inner_loop) { if( abs(arr[outer_loop] - arr[inner_loop]) < diff) { diff = abs (arr[outer_loop] - arr[inner_loop]); element_1 = arr[outer_loop]; element_2 = arr[inner_loop]; } } } printf("The least difference is %d between the elements %d and %d \n", diff, element_1, element_2 ); } int main(int argc, char const *argv[]) { int arr [100] = {6, 10, 5, 42, 43, 1, 2}; int length = 7; getLeastDifference(arr, length); return 0; }
Output:
The least difference is 1 between the elements 6 and 5
Solution 2:
The first step is to sort the given array.
Then check the difference between the elements and update them.
The efficiency will be O(n log n)
Below is 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 getLeastDifference(int arr[], int lenght) { int diff = INT_MAX; int itr = 0; int element_1 = 0; int element_2 = 0; for ( itr = 0; itr < lenght - 1; itr++) { if (arr[itr+1] - arr[itr] < diff) { diff = arr[itr+1] - arr[itr]; element_1 = arr[itr+1]; element_2 = arr[itr]; } } printf("The least difference is %d between the elements %d and %d \n", diff, element_1, element_2 ); } int main() { int arr [100] = {6, 10, 5, 42, 43, 1, 2}; int length = 7; bubble_sort(arr, length); getLeastDifference(arr, length); }
Output:
The least difference is 1 between the elements 2 and 1
Amit kumar
First:- Sort it in increasing order…print the difference of first two elements..O(nlogn)
Second:- try to find the two minimum value from the array and print the difference.O(n)
Amit kumar
Sorry..wrongly I understood the qsn..
Amit kumar
I can only do in order of O(n^2)
Anyone if solve In less time complexity please share.
Amit kumar
Yes,O(nlogn+n) is possible…
Sort then take adjacent difference and from there minimum.
Goku007
I guess answer should be the difference of 2 minimum values. Sort the array in increasing order and print difference of 1st and 2nd element.
Amit kumar
Nope..
E.g 1,3,44,45
Min difference is 1 not 2.
Devendra Kumar
Solution 2 , which is given has also n^2 complexity..
Because it uses bubble short…..
Counting short may useful…
sudhir
we don’t need to sort the array we can just do the second part as given below which result in O(n).
but the issue is it will return the first pair which has lowest difference. but could be solved just by replacing in if ,instead of < use <=
def diff(arr):
min=float('inf')
for i in range(len(arr)-1):
if abs(a[i]-a[i+1])<min:
min=abs(a[i]-a[i+1])
ele1=a[i]
ele2=a[i+1]
return min,ele1,ele2
a=[6,10,5,42,43,1,2]
print(diff(a))