The logic will be first to find out the min difference. Then to find all pairs with their sum equal to the min difference.
#include #define MAX 10000 #define bool int void findPair(int arr[], int arr_size, int sum) { int i,temp; bool binMap[MAX]={0}; /*Initialize hasmap with 0*/ printf("Numbers with minimum difference %d are\n", sum); for(i=0; i=0 && binMap[temp]==1) { printf("%d %d\n", arr[i],temp); } binMap[abs(arr[i])]=1; } }
void minDiff(int arr[], int arr_size) { int min_diff = arr[1] - arr[0]; int max_element = arr[0]; int i; int start=arr[0], end=arr[1]; for(i = 1; i < arr_size; i++) { if(arr[i] - max_element < min_diff) { min_diff = arr[i] - max_element; start=max_element; end=arr[i]; } if(arr[i] > max_element) max_element = arr[i]; } findPair(arr, arr_size,min_diff); }
/* Driver program to test above function */ int main() { int arr[] = {-520,-470,-20,30} ; int size = sizeof(arr)/sizeof(arr[0]); minDiff(arr, size); getchar(); return 0; }
Output: Numbers with minimum difference 50 are -470 520 30 20
The logic will be first to find out the min difference. Then to find all pairs with their sum equal to the min difference.
ReplyDelete#include
#define MAX 10000
#define bool int
void findPair(int arr[], int arr_size, int sum)
{
int i,temp;
bool binMap[MAX]={0}; /*Initialize hasmap with 0*/
printf("Numbers with minimum difference %d are\n", sum);
for(i=0; i=0 && binMap[temp]==1)
{
printf("%d %d\n", arr[i],temp);
}
binMap[abs(arr[i])]=1;
}
}
void minDiff(int arr[], int arr_size)
{
int min_diff = arr[1] - arr[0];
int max_element = arr[0];
int i;
int start=arr[0], end=arr[1];
for(i = 1; i < arr_size; i++)
{
if(arr[i] - max_element < min_diff)
{
min_diff = arr[i] - max_element;
start=max_element;
end=arr[i];
}
if(arr[i] > max_element)
max_element = arr[i];
}
findPair(arr, arr_size,min_diff);
}
/* Driver program to test above function */
int main()
{
int arr[] = {-520,-470,-20,30} ;
int size = sizeof(arr)/sizeof(arr[0]);
minDiff(arr, size);
getchar();
return 0;
}
Output: Numbers with minimum difference 50 are
-470 520
30 20
Time complexity: 0(n)
Ideone link: http://ideone.com/YgeCot