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?