How to find in one loop biggest difference between all pairs in array

Question

I have an exercise in Java, writing a method (as followed) that receives as parameters an array with numbers and int x and returns true if there is in the array pair of numbers (not has to be in the following order) that its absolute difference is bigger than x.

for example for the array {1, 5, 2, 18, 4, 2, 11} and I can use one loop only. thank you for your help

public boolean difference (int[] a, int x)

Answer 1

Finding the largest difference between all pairs of numbers in an array is the same as finding the difference between the largest and smallest value. So you only need to find the largest and smallest value. Naturally, Java does this for you already:

import java.util.Arrays;
import java.util.IntSummaryStatistics;

public class Main {
    public static void main(String[] args) {
        int[] a = {1, 5, 2, 18, 4, 2, 11};
        System.out.println(difference(a, 16));
        System.out.println(difference(a, 17));
    }

    public static boolean difference(int[] a, int x) {
        IntSummaryStatistics stat = Arrays.stream(a).summaryStatistics();
        return (stat.getMax() - stat.getMin()) > x;
    }
}

This produces the following output:

true
false

Answer 2

Here is a slightly different approach.

    public static void main(String[] args) {
        int[] a = {1,2,3,4,5,6,7};
        System.out.println(difference(5,a));
    }

    static boolean difference(int[] a, int x) {
        int min = a[0];
        int max = min;
        for (int i = 1; i < a.length; i++) {
            int v = a[i];
            if (v < min) {
                min = v;
            } else if (v > max) {
                max = v;
            }
            // check here since it may not be 
            // necessary to iterate thru all values.

            if (max - min > x) {
                return true;
            }
        }    
        return false;
    }

It is optimized in several ways.

1. Min and max are set to the first element in the list. So iteration starts at the second item.
2. Since you don't need the widest difference, the delta of min and max is checked on each iteration since it may not be necessary to iterate over the entire list.
3. And since by definition, max > min, the absolute value is implicit, even for negative numbers.

Answer 3

• Declare two integers, one with the max value an int can be, one with the min value an int can be

• Use one loop to iterate the array

  • If the current element is greater than the min, make the min equal to the current element
  • If the current element is less than the max, make the max equal to the current element

• When the loop is finished work out the difference between min and max

• Print a message if the difference is greater than X

I haven't written the java for you because I think this is an academic exercise, possibly homework. You'll get more out of it as a learning exercise if you do it yourself - take this algorithm, put it as comments and write the code for it. We (and your supervisor) will be here for you if you get stuck. Think of the comments as like when doing an exam and the invigilator/tutor says "show your working" - showing your working is important because:

• You can still get points for having the right idea even if its the wrong implementation
• Your tutor can see where you went wrong, which is also feedback for better teaching and for your specific learning
• Like creating a plan to write an essay, comments of the algorithm help avoid bugs and help prevent you forgetting what each section of code is supposed to do. I'ts easy to get lost when trying to write a new language as well as devise an algorithm

Always write comments

Answer 4

Algorithm : Have a smallest and largest variable initialised to smallest and greatest possible values. Loop through all elements and if smaller than smallest or greater than greatest update the respective variables. Then at the end of the loop compare x to greatest - smallest.