Duplicate like a weapon, arrays like heaven Challenge:


  Find the duplicated entry.


Specifications:


  Your program should accept as its first argument a path to a filename.
  Each line in this file is one test case.  
  
  Each line begins with a positive integer(N), the size of the array,
  then a semicolon followed by a comma separated list of positive numbers
  which range from 0 to N-2, inclusive.
  
  The array contains exactly one duplicated entry which appears exactly twice.
  Print out the duplicated entry, each one on a new line.


Solution:

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

public class ArrayAbsurdity {
    public static void main(String[] argument) throws FileNotFoundException {
        Scanner input = new Scanner(new File(argument[0]));
        String[] args;

        while (input.hasNextLine()) {
            args = input.nextLine().split(";");
            printDuplicate(args[0], args[1].split(","));
        }
    }

    private static void printDuplicate(String size, String[] nums) {
        boolean[] absurd = new boolean[Integer.parseInt(size)];
        int value;
        Arrays.fill(absurd, false);

        for (int i = 0; i &lt; absurd.length; i++) {
            value = Integer.parseInt(nums[i]);

            if (absurd[value]) {
                System.out.println(value);
                break;
            }

            absurd[value] = true;
        }
    }
}


Sample Input:


  5;0,1,2,3,0
  20;0,1,10,3,2,4,5,7,6,8,11,9,15,12,13,4,16,18,17,14


Sample Output:


  0
  4


I usually write two auxiliary methods, but this time I did some of the work within main's loop, and only wrote one print method. Does the print method do too much? With and without considering its name.

I was going to use two arrays and/or two loops at first, but considering all that was given the question's purpose surely is to create the most efficient solution and thanks to learning of Arrays.fill on one of my previous answers, courtesy of @rolfl, I came up with this. Is it optimal?

For anyone interested, I maintain my current implementation here, and the implementation of the accepted answer here, also the source for the title since a few people asked in chat.
@tim suggested a way to do this with less memory by sorting the array. There's another way to do it with less memory without needing to sort.

Let's say that \$k\$ is the duplicate value in the array. Then we know that the sum of the elements in the array is equal to

\begin{align}
0 + 1 + 2 + 3 + \cdots + (n - 2) + k = \frac{(n - 2)(n - 1)}{2} + k,
\end{align}

where we're using the identity

\begin{align}
1 + 2 + 3 + \cdots + n = \frac{n (n + 1)}{2}.
\end{align}

So if sum is the sum of the values in the array, the duplicate value will be sum - (n - 2) * (n - 1) / 2.