Why is my program for, minimum difference between ANY TWO elements in an array, giving opposite result?

Question

This might sound like a repeat question but it is not because I haven't found the answer to my question in-spite of going through several references/related questions as listed below (and a lot more not listed).

Minimum difference in an array

Finding out the minimum difference between elements in an array

Find the minimum difference between two arrays

Dividing an array into two subsets of equal sizes having minimum difference in sum of values

http://www.geeksforgeeks.org/find-the-minimum-distance-between-two-numbers/

http://programmingpraxis.com/2013/10/15/find-the-minimum-difference/#comment-9146

https://www.daniweb.com/programming/software-development/threads/391082/distance-between-two-closest-elements-in-an-array

Following is my program and my own attempt to try and find the "Minimum difference between two elements within the array, any two pairs", then let be there more than one pair of numbers which gives the same minimum difference numerically. I tried to change loops to count them differently and also tried to change the if condition clause for different results but finally ended up with the following code:

#include <iostream>                     //input output stream   
#include <cstdlib>
#include "math.h"                       //to be able to use math functions if any


using namespace std;

int main()

{

    
    int x=0,y=0,number1 = 0,number2 = 0,size1=0,mindiff = 0;
    int index = 0, count = 0, diff = 0;
    cout<<"enter the size of array you want \n\n";
    cin>>size1;
    int arr1[size1];
    cout<<"\n\n please enter elements of array \n\n";
    
    for (int i =0;i<size1;i++)
    {
        cin>>arr1[i];
    }
    for ( x=0;x<size1;x++ )
    {
        diff = 0;
        for ( y=0;y<size1;y++ )
        {
            diff = abs(arr1[x] - arr1[y]);
            if (diff<mindiff)
            {
                mindiff = diff;
                //index = x+1;
                number1 = arr1[x];
                number2 = arr1[y];
            }
        }
            
        }   


cout<<"\nthe elements amongst which the minimum difference was given are "<<number1<<" & "<<number2<<endl;
cout<<"the difference between them is "<<abs(mindiff)<<endl;
    
system("pause");
return 0;
}


//end of program

All the above references and lots more but could not find anyone that follows my perspective. I know that i may be doing something really silly/wrong out here because i get a maximum difference and not minimum difference.Where am I going wrong? I anyways have to keep on assigning the new minimum every time a lower difference is found as written in the if condition statement right???

following is the output

enter the size of array you want

6

please enter elements of array

1 2 34345 7 8 9

the elements amongst which the minimum difference was given are 1 & 34345 the difference between them is 34344

Press any key to continue . . .

What numbers did you use, what result did you expect, and what result did you get? — Beta, Jan 25 '16 at 23:04
@CodeMan you can, but it will be O(N^2), sorting will give you O(NlogN). — SashaMN, Jan 25 '16 at 23:13
It amazes me that you use abs to report the result, but not in the calculation. I suggest you close this question, as it is unlikely to help future readers. — Beta, Jan 25 '16 at 23:14
yes but it also amazes me that by changing that it still gives me the same maximum difference result instead of minimum difference result. — Code Man, Jan 25 '16 at 23:44
@SashaMN that will be fine for now i just need to see if the logic works, so far it has not worked — Code Man, Jan 25 '16 at 23:48
Put a `cout` statement in your innermost loop: `cout << arr1[x] << " " << arr[y] << " " << diff << endl;`. This will tell you what is actually happening. And remove the `abs` from your final output code. And try it with **two** numbers, before you attempt six. — Beta, Jan 26 '16 at 01:21
yes, that helps me identify the point at which my code works weird......thnx — Code Man, Jan 26 '16 at 02:58

score 2 · Answer 1 · answered Jan 25 '16 at 23:07

2

Use the abs(x) function to make sure that diff is positive. Otherwise, the difference between arr1[x]:5 and arr1[y]:10 (5-10=-5) will be smaller than the difference between arr1[x]:5 and arr1[y]:4 (5-4=1).

http://www.cplusplus.com/reference/cstdlib/abs/

You also want to make sure that you never check with the same index, i.e. x=y.

answered Jan 25 '16 at 23:07

david

292
5
20

oh yes that does help because it would otherwise report zero everytime.....but it still gives a maximum difference now am planing to use abs in the loop – Code Man Jan 25 '16 at 23:41

Bob__ · Answer 2 · 2016-01-26T16:51:24.670

You can improve your algorithm a little bit (halving the comparisons, actually) by considering the underlying simmetry:

#include <iostream>
#include <limits>

using std::cout;

// I'll use a struct to return the values
struct dif_t {
    int first;
    int second;
    int dif;
};

dif_t min_difference( const int *x, size_t n ) {
    dif_t min{0,0,0};
    min.dif = std::numeric_limits<int>::max();

    for ( size_t i = 0; i < n; ++i ) {
        //remember that abs(x[i]-x[j])=abs(x[j]-x[i]) and x[i]-x[i]=0
        for ( size_t j = i + 1; j < n; ++j ) {
            //          ^^^^^^^
            int dif = abs( x[i] - x[j] );
            if ( dif < min.dif ) {
                min.dif = dif;
                min.first = x[i];
                min.second = x[j];
            }
        }
    }
    return min;
}

int main() {
    // I'll skip the input part
    int numbers[] = { 1, 20, 34345, 89, 7, 88 };

    dif_t edif = min_difference(numbers, sizeof(numbers)/sizeof(int));

    std::cout << "The elements with the minimum difference are:\n"
        << edif.first << " and " << edif.second << '\n'
        << "The difference between them is:\n" << edif.dif << '\n';

    return 0;
}

If you want to find all the pairs with the same minimum difference you can modify the previous program like this:

#include <iostream>
#include <limits>
#include <vector>
#include <utility>

using std::cout;
using std::vector;
using std::pair;


struct dif_t {
    vector<pair<int,int>> pairs;
    int dif;
};

dif_t min_difference( const vector<int> &x ) {
    dif_t min;
    min.dif = std::numeric_limits<int>::max();

    for ( size_t i = 0; i < x.size(); ++i ) {
        for ( size_t j = i + 1; j < x.size(); ++j ) {
            int dif = abs( x[i] - x[j] );
            if ( dif > min.dif ) continue;
            // if the difference is less then the minimum, empties the container
            if ( dif < min.dif ) {
                min.dif = dif;
                min.pairs.clear();
            }
            // add the couple to the vector
            min.pairs.push_back(std::make_pair(x[i], x[j]));
        }
    }
    return min;
}

int main() {
    vector<int> numbers = { 1, 2, 4, 34345, 34346, 6, 89, 7, 88 };

    dif_t edif = min_difference(numbers);

    cout << "The elements with the minimum difference are:\n";
    // loop for each couple in the container
    for ( auto & c : edif.pairs ) {
        cout << c.first << " and " << c.second << '\n';
    }       
    cout << "The difference between them is:\n" << edif.dif << '\n';

    return 0;
}

Which outputs:

The elements with the minimum difference are:
1 and 2
34345 and 34346
6 and 7
89 and 88
The difference between them is:
1

If the number of elements is bigger, as others pointed out, you can sort the vector before calculating the differences, so you will minimize the comparison needed.

// this will change the original vector
dif_t min_diff_sorted( vector<int> &x ) {
    // erase the reference symbol  ^ if you want to sort a copy of the vector 
    dif_t min;
    min.dif = std::numeric_limits<int>::max();

    // usually sorting algorithms have N*logN complexity 
    std::sort( x.begin(), x.end() );

    // now that the vector is sorted we can compare the adiacent elements only.
    // This time I'll use two iterators to access the elements of the vector
    // ix will iter from the beginning of the vector to the last - 1 element
    // jx points to the element adjacent (+1) to ix
    for ( auto ix = x.begin(), jx = ix + 1;
            jx != x.end();      // stop condition
            ix = jx, jx++ ) {
        // the inner part doesn't change, it's only executed N-1 times 
        // instead of N*(N-1)/2                 
        int dif = abs( *ix - *jx );
        if ( dif > min.dif ) continue;
        if ( dif < min.dif ) {
            min.dif = dif;
            min.pairs.clear();
        }
        min.pairs.push_back(std::make_pair(*ix, *jx));
    }
    return min;
}

wholly chao Bob, my sincere gratitude for the effort, i needed the extended features...However i was trying to figure out a way to do the original task without using special libraries....But i like the extended improv....d| d| d| — Code Man, Jan 28 '16 at 07:05
@CodeMan You're welcome. Please note that the "special libraries" are the C++ Standard Library, which is literally part of the language ;) You can use plain arrays, of course, (and try to implement a good sort) but that way is more error prone, and not so easy as you may think. — Bob__, Jan 28 '16 at 16:41

score 1 · Answer 3 · answered Jan 26 '16 at 00:02

You can calculate mindiff at start as abs(arr1[0]-arr1[1]) and then proceed to calculate it inside the loop:

 // check whether array size is >=2 or not
    mindiff = abs(arr1[0]-arr1[1]);

    for ( x=0;x<size1;x++ )
    {
        for ( y=0;y<size1;y++ )
        {
           // do not calculate the difference of same number
            if(x!=y){
                diff = abs(arr1[x] - arr1[y]);
                if (diff<=mindiff)
                {
                    mindiff = diff;
                    number1 = arr1[y];
                    number2 = arr1[x];
                    cout<<number1<< ","<<number2<<endl;
                }
           }
        }
      }   

 cout<<"\nthe elements amongst which the minimum difference was given are "<<number1<<" & "<<number2<<endl;

cout<<"the difference between them is "<<abs(mindiff)<<endl;

score 0 · Accepted Answer · answered Jan 26 '16 at 08:57

Taking the advice from Beta and also looking at the only answer that i found aligning with my code perspective, i came up with the following smal but critical edit of my own code above. Not much change but a very important and essential change. PFB the code which indicates that fact that i had a logical error in not loading the difference value temporarily in a variable before exiting the innermost loop for the next iteration for comparing the absolute difference value.

#include <iostream>                             //input output stream   
#include <cstdlib>
//#include <vector>         not used            //to enable usage and implementation of vectors
#include "math.h"                               //to be able to do complex math functions if any
//#include <algorithm>      not used            //to be able to use max_element() and distance() functions on iterator.


using namespace std;

int main()

{

/*
first different variables for loop counters and 
size of array is taken in advanced instead of calculating during the program to reduce program time

*/

    int x=0,y=0,number1 = 0,number2 = 0,size1=0,mindiff = 0;
    int index = 0, count = 0, diff = 0;
    cout<<"enter the size of array you want \n\n";
    cin>>size1;
    int arr1[size1];
    cout<<"\n\n please enter elements of array \n\n";

    for (int i =0;i<size1;i++)
    {
        cin>>arr1[i];
    }
    for ( x=0;x<size1;x++ )
    {

        for ( y=0;y<size1;y++ )
        {
        if (x!=y)
/*
now load the difference in a variable named diff
and use a comparisional conditional statement to select
value of minimum difference
*/
            {
            diff = abs(arr1[x] - arr1[y]);
                if(count == 0)
                {
                    mindiff = diff;
                }
            else
                {
                    if (diff<mindiff)
                    {
                    cout<<diff<<" minimum difference "<<"\n";
                    mindiff = diff;
                    //index = x+1;
                    number1 = arr1[x];
                    number2 = arr1[y];
                    }
                }
            count++;
            }
        }

    }


cout<<"\nthe elements amongst which the minimum difference was given are "<<number1<<" & "<<number2<<endl;
cout<<"the difference between them is "<<abs(mindiff)<<endl;
cout<<endl<<endl;

system("pause");

return 0;
}

This lets me perceive that perspective of coding does work for this case. Sure it might be slow and inefficient but its a result. gratitude to all for their time.

Why is my program for, minimum difference between ANY TWO elements in an array, giving opposite result?

4 Answers4