If the array elements are positive numbers and also elements are in the range 0 to n-1 , then we can find duplicate elements using negation technique. For each element a[i], go to the array element whose index is a[i], that means we select a[a[i]] and mark this value as -a[a[i]]. That is we negate the value of a[a[i]. Continue this process until we find the element that is already negated.

**Note:**

- The solution does not work if the given array is read only, that means no manipulation is allowed to array elements.
- The solution will work only if the array elements are positive and are in the range 0 to n-1.

**Finding duplicates in an array using negation – O(n)**

/** * <p>Check Duplicates in the array using Math abs</p> * Time Complexity ::O(n) * Space Complexity ::O(1) * @param a * @return */ public static int checkDuplicatesWithMathAbs(int[] a){ int n=a.length; for(int i=0;i<n;i++){ if(a[Math.abs(a[i])]<0) return a[i]; else a[a[i]]=-a[a[i]]; } return -1; }

Sample **Test Client** for above program

public static void main(String[] args) { /** * Checking duplicates in the array by placing negative values * Array elements should be in the range 0 to n-1 * This solution does not work if the given array is read only and all the * elements should be +ve * Time Complexity :: O(n) * Space Complexity :: O(1) */ int[] arr5={0,1,2,2,4,5,6}; System.out.println(checkDuplicatesWithMathAbs(arr5)); }