Find the number of times that the difference of array values are equal to the number

Question

I wrote the following code to answer this, but I am wondering if there is any better approach.

For example

If the following array is given:

{10,21,34,45,56}

we should find the differentiate of each number with other values of the array and in case it is equals to 11 should increment the counter.

10-21=-11
10-34=-24
10-45=-35
10-56=-46
21-10=11     <
21-34=-13
21-45=-24
21-56=-35
34-10=24
34-21=13
34-45=-11
34-56=-22
45-10=35
45-21=24
45-34=11   <<
45-56=-11
56-10=46
56-21=35
56-34=22
56-45=11   <<<

Code

List<Integer> a = new ArrayList<Integer>();
       a.add(10);
       a.add(21);
       a.add(34);
       a.add(45);
       a.add(56);
      int number = 11;
      int counter = 0;
       for(int i=0;i<a.size();i++){
           for(int j=0;j<a.size();j++){
               if(j!=i){
                   int t = a.get(i) - a.get(j);
                   if(t == number){
                       System.err.println(a.get(i) +"-"+ a.get(j) + "=" + t);
                       counter++;
                   }
               }
           }
       }
       System.err.println(counter);
    }

Output

The application is correctly showing the results but I am wondering if there is any other approach to the above solution.

21-10=11
45-34=11
56-45=11
3

Answer 1

I think you should look at the problem in a different way and come up with a simpler solution.

Try thinking at having a set of elements. What you want to know is if there is any pair of elements such that a - b = x.

You're given x, so for a given value of a in your set you should check whether it also contains x + a.

Your implementation should first move the content of the list to a Set. Then you have to iterate through the set and for each element a check if the set contains also x + a. If it is true then you should add (a,b) to your solution.

In your example, x = 11. If you consider a = 10 you'll check if it contains 11 + 10 = 21. It does so you can the pair (21,10) is a valid solution. Conversely, when you consider a = 21, you obtain b = 32, which is not part of the set and therefore you have to discard that pair.

int checkDifferences(Set<Integer> numbers, int difference) {
    int occurrences = 0;
    for (Integer number : numbers) {
        if (numbers.contains(number + difference)) {
            occurrences++;
        }
    }
    return occurrences;
}

Answer 2

Initialize List

Your List<Integer> can be initialized as the following:

 List<Integer> a = Arrays.asList(10, 21, 34, 45, 56);

Actually, as you are dealing with a fixed-length size list, you can just use a regular array.

 int[] a = new int[]{ 10, 21, 34, 45, 56 };

Spacing

I strongly recommend using more space in your for-loops:

   for (int i = 0; i < a.size(); i++) {
       for (int j = 0; j < a.size(); j++) {
           if (j != i) {

Isn't that more readable? At least it is to me.

Variable names

You are using way too many variable names with only one letter. I suggest renaming them like this:

• a --> numbers
• i --> firstNumber
• j --> secondNumber
• t --> difference

Answer 3

The int values will be autoboxed here:

List<Integer> a = new ArrayList<Integer>();
a.add(10);
a.add(21);
// ...

And then unboxed here in every iteration of the nested for for:

int t = a.get(i) - a.get(j);

To avoid that inefficiency it would be better to use a primitive array instead:

int[] a = { 10, 21, 34, 45, 56 };

Answer 4

If I were to improve on your original solution, I will use if ( j == i ) to eliminate one nested if and inline the arithmetic comparison together with incrementing counter as shown below:

private static void originalCheck( final List<Integer> list, final int difference ) {
    int counter = 0;
    for ( int i = 0 ; i < list.size() ; i++ ) {
        for ( int j = 0 ; j < list.size() ; j++ ) {
            if ( j == i ) {
                continue;
            }
            if ( list.get( i ) - list.get( j ) == difference && ++counter > 0 ) {
                System.err.println( String.format( "%d - %d = %d", list.get( i ), list.get( j ), difference ) );
            }
        }
    }
    System.err.println( counter );
}

If I have to implement an alternative solution, I will consider storing the numbers seen inside a Map so that I avoid traversing the full List twice. The inner for-loop will always start from the next index. The method to create the Map and the method to print the entries of the Map are shown below:

private static Map<Integer, Integer> checkDifference( final List<Integer> list, final int difference ) {
    final Map<Integer, Integer> result = new LinkedHashMap<>();
    for ( int i = 0 ; i < list.size() ; i++ ) {
        for ( int j = i + 1 ; j < list.size() ; j++ ) {
            final Integer first = list.get( i );
            final Integer second = list.get( j );
            final int diff = first - second;
            if ( Math.abs( diff ) == difference ) {
                result.put( diff > 0 ? first : second, diff > 0 ? second : first );
            }
        }
    }
    return result;
}

private static void printDifference( final Map<Integer, Integer> result ) {
    for ( final Entry<Integer, Integer> entry : result.entrySet() ) {
        final int difference = entry.getKey() - entry.getValue();
        System.err.println( String.format( "%d - %d = %d", entry.getKey(), entry.getValue(), difference ) );
    }
    System.err.println( result.size() );
}