5
\$\begingroup\$

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
\$\endgroup\$
7
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ is not that wrong, as Set requires reference \$\endgroup\$ – Jack Sep 16 '14 at 22:24
  • \$\begingroup\$ I wrote this Set<Integer> a = new HashSet<Integer>(); a.add(10); a.add(21); a.add(34); a.add(45); a.add(56); int number = 11; int counter = 0; Iterator it = a.iterator(); while(it.hasNext()){ Integer inte = (Integer) it.next(); if(a.contains(inte + number)){ counter++; } } System.err.println(counter); } \$\endgroup\$ – Jack Sep 16 '14 at 22:24
  • 2
    \$\begingroup\$ Wait, I just added a method. Not the whole program. The reason I did is that it is always a good idea to separate things in different pieces instead of having everything on the main method. Putting everything together should be trivial. \$\endgroup\$ – mariosangiorgio Sep 16 '14 at 22:29
  • 5
    \$\begingroup\$ @Jack This answer should have given you a good starting point for how to improve your code. Reviewers have no obligation to provide you with the final result, I suggest that you spend some more time reading and understanding the answer and trying to make your code better with this answer in mind. It is, after all, your code. \$\endgroup\$ – Simon Forsberg Sep 16 '14 at 22:42
  • 4
    \$\begingroup\$ The Set Contract does not allow duplicate items.. this is undesired behavior. Think number = 0... while your approach is intersting it doesn't solve the problem... \$\endgroup\$ – Vogel612 Sep 16 '14 at 23:20
7
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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 };
\$\endgroup\$
2
\$\begingroup\$

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() );
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.