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