/**
 * You are given a list of numbers from 0..N; Each element on the array has
 * a number that goes from 0..N. Find if the array has any duplicates on it.
 * Well, for this problem I'm going to assume that CPU power is not an issue
 * but storage space. Also will try to keep access to the list to the minimun.
 *
 * @author Jose V Nunez Zuleta
 * @version 0.1 - 02/28/2005
 * License: GPL
 * Blog: El Angel Negro - http://elangelnegro.blogspot.com
 */
public class ArrayDuplicate {
        
        /**
         * So the idea is to count how many ocurrences of the number appears.
         * We have to scan the whole list in order to find duplicates, so the
         * worst case is log(n). We will use the fact that each number can be
         * stored as a mask of bits, and based on the position from 0 to N we 
         * can have each number as f(n)=2^(n-1). We are only interested to see 
         * if there is a duplicate, so we don't really care about the real number
         * of duplicates.
         *
         * @param args - List of unsorted numbers
         * @throws Exception if the numbers are invalid
         * @since 0.1
         */
        public static void main(String [] args) throws Exception {
                if (args == null) {
                        throw new 
                                IllegalArgumentException("Provide some numbers");
                }
                
                if (args.length == 0) {
                        throw new 
                                IllegalArgumentException("Provide some numbers");
                }
                int len = args.length;
                
                int num = 0;
                int checksum = 0;
                for (int i = 0; i < len; i++) {
                        num = Integer.parseInt(args[i]);
                        int mask = numMask(num);
                        // This number is not on the list, so add it!
                        if ( (checksum & mask) == 0 ) {
                                checksum |= mask;
                        } else {
                                System.out.println("Found first duplicate: " 
                                        + num);
                                        break;
                        }
                }
        }
        
        /**
         * f(n)=2^(n-1)
         * @param number
         * @return int
         */
        public static int numMask(int number) {
                return 1 << number;
        }
        
}