Array absurdity challenge

Question

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<a.length-1; i++){
                for(int j=i+1; j<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?

Answer 1

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<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.

Answer 2

Apparently according to this post String tokeniser performance using indexOf is alot quicker (I personally have no idea on that front). So taking what the chap posted in his solution you might be able to do something like:

String[] in = str.split(";");

// I assumed that in alot of the cases we will find the duplicate with at least  n / 2 checks
int initialCapacity = Integer.parseInt(in[0]);

HashMap<String,Boolean> items = new HashMap<String,Boolean>(initialCapacity / 2);

int pos = 0, end;
String sample = in[1];
boolean foundDuplicate = false;

while ((end = sample.indexOf(',', pos)) >= 0) {
    // assuming uniform data with no extra spaces etc do we even need to parse
    // the value to an integer?
    String item = sample.substring(pos, end);

    if(items.containsKey(item)) {
        System.out.println(item);
        foundDuplicate = true;
        break;
    } else {
        items.put(item, true);
    }

    pos = end + 1;
}

if(!foundDuplicate) {
    System.out.println(sample.substring(pos)); // must be the last item
}