Array absurdity challenge This is a CodeEval challenge taken from here:


  Challenge description:
  
  Imagine we have an immutable array of size N which we know to be
  filled with integers ranging from 0 to N-2, inclusive. Suppose we know
  that the array contains exactly one duplicated entry and that
  duplicate appears exactly twice. Find the duplicated entry. (For bonus
  points, ensure your solution has constant space and time proportional
  to N)
  
  Input sample:
  
  Your program should accept as its first argument a path to a filename.
  Each line in this file is one test case. Ignore all empty lines. Each
  line begins with a positive integer(N) i.e. the size of the array,
  then a semicolon followed by a comma separated list of positive
  numbers ranging from 0 to N-2, inclusive):

1
2
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

  
  Output sample:
  
  Print out the duplicated entry, each one on a new line:

1
2
0
4



I've written this code:

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.StringTokenizer;

/**
 *
 * @author Mohammad Faisal
 */    
public class ArrayAbsurdity {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner input = new Scanner(new FileInputStream("E:\\java\\temp\\abc.txt"));
        while(input.hasNextLine()){
            String str = input.nextLine();
            if(str.equals("")){
                continue;
            }
            String[] in = str.split(";");
            int i=0;
            int[] a = new int[Integer.parseInt(in[0])];
            StringTokenizer token = new StringTokenizer(in[1], ",");
            while(token.hasMoreTokens()){
                a[i]=Integer.parseInt(token.nextToken());
                i++;
            }

            boolean success=false;
            for(i=0; i&lt;a.length-1; i++){
                for(int j=i+1; j&lt;a.length; j++){
                    if(a[i] == a[j]){
                        System.out.println(a[i]);
                        success=true;
                        break;
                    }
                }
                if(success){
                    break;
                }
            }
        }
    }
}


Can anybody review it and help me in improving the space and time complexity as per the problem?
I don't have a comment on how you parse the input. I just give a solution which runs in O(1) space and O(N) time.

Problem says that all integers are in range 0..N-2 and there's only one integer duplicated. Consider you hadn't that duplicated element, so sum of all input numbers would be (n-2)*(n-1)/2 (sum of integers from 0 to n-2). So now you can read all N integers and calculate their sum. Then if you subtract (n-2)*(n-1)/2 from this sum, the value of your duplicated element would come out.

The code would be:

int sum = 0;
int n = a.length;
for(i=0; i&lt;n; i++)
  sum += a[i];

System.out.println(sum - (n-2)*(n-1)/2);


This method is clearly of O(n) time, but if you want to achieve O(1) space, you should avoid storing all elements in an array. Instead of that, when you parsed nextToken, you add it to sum.