Monday, October 26, 2015

Finding duplicate from array having element from 0 to n-2.


An array contains n numbers ranging from 0 to n-2. There is exactly one number duplicated in the array. How do you find the duplicated number? For example, if an array with length 5 contains numbers {0, 2, 1, 3, 2}, the duplicated number is 2. Solution:

class Solution {
    public static int findDuplicate(int numbers[]) {
        int length = numbers.length;
        int sum1 = 0;
        for (int number : numbers) {
            if (number < 0 || number > length - 2)
                throw new IllegalArgumentException("Invalid numbers.");
            sum1 += number;
        }
        // Calcualate the sum of number from 1 to n as n(n-1)/2  
        int sum2 = ((length - 1) * (length - 2)) >> 1;
        return sum1 - sum2;
    }
    public static void main(String[] args) {
        int input[] = {0, 2, 1, 3, 2};
        System.out.println("Duplicate Number : " + findDuplicate(input));
    }
}

//Output of above code will be 
Duplicate Number : 2

No comments:

Post a Comment