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?

When you look at the array, a pattern becomes evident: The difference between consecutive elements is 111. Therefore, the difference between two elements is a function of how far apart they are in the array. If two elements are identical, the difference is 0; if they're adjacent, it's 111; if they're separated by one element, it's 222; and so on. It would appear that the number of differences is the same as the number of distances, which is the size of the array, or 8. If you ran the program, however, you found that it prints 14. What's going on?

This analysis contains one small flaw. To investigate the flaw, we can print out the contents of the set by removing the characters .size() from the println statement. Doing this produces the following output:

[111, 222, 446, 557, 668, 113, 335, 444, 779, 224, 0, 333, 555, 666]

Not all these numbers are multiples of 111. There must be two adjacent elements in the vals array whose difference is 113. If you look at the array declaration, it may not be clear why this is so:

int vals[] = { 789, 678, 567, 456,

               345, 234, 123, 012 };

But if you print the contents of the array, here is what you will see:

[789, 678, 567, 456, 345, 234, 123, 10]

Why is the final element of the array 10 instead of 12? Because integer literals beginning with a 0 are interpreted as octal values [JLS 3.10.1]. This obscure construct is a holdover from the C programming language. C dates from the 1970s, when octal was much more commonly used than it is today.

Once you know that 012 == 10, it is obvious why the program prints 14: There are 6 unique nonzero differences not involving the final array element, 7 unique nonzero differences involving the final array element, and there is zero, for a total of 14 unique differences. It is even more obvious how to fix the program: Replace the octal integer literal 012 with the decimal integer literal 12. If you do this, the program will print 8 as expected.

The lesson of this puzzle is simple: Never pad an integer literal with zeros; this turns it into an octal literal. The intentional use of octal integer literals is so rare that you should probably comment every use. The lesson for language designers is to exercise restraint when deciding what features to include. When in doubt, leave it out.