Library Puzzlers - Java Puzzlers: Traps, Pitfalls, and Corner Cases - page 171

< Day Day Up >
Puzzle 59: What's the Difference?
This program computes the differences between pairs of elements in an int array, puts these
differences into a set, and prints the size of the set. What does the program print?
import java.util.*;
public class Differences {
public static void main(String[] args) {
int vals[] = { 789, 678, 567, 456,
345, 234, 123, 012 };
Set<Integer> diffs = new HashSet<Integer>();
for (int i = 0; i < vals.length; i++)
for (int j = i; j < vals.length; j++)
diffs.add(vals[i] - vals[j]);
System.out.println(diffs.size());
}
}
Solution 59: What's the Difference?
The outer loop iterates over every element in the array. The inner loop iterates over every element
from the current element in the outer-loop iteration to the last element in the array. Therefore, the
nested loop iterates over every possible pair of elements from the array exactly once. (Elements may
be paired with themselves.) Each iteration of the nested loop computes the (positive) difference
between the pair of elements and stores that difference in the set, which eliminates duplicates.
Therefore, this puzzle amounts to the question, How many unique positive differences are there
between pairs of elements from the vals array?