Find Duplicate Elements in an Array with elements in given range

Given an array of size n. It contains numbers in the range 1 to n. Each number is present at least once except for 2 numbers. Find the missing numbers.

Solution:

(Note: Here we make assumption that all the elements in array are positive.  For solution of finding duplicate in array where range is not given, visit here).

The main idea of the solution is to make use of the fact that the given numbers are in given range n and the size of the array is also n.  Basically we can map each element's value with the index of the array to create a key-value relation.

//Start iterating from first element of the array.
for(int i=0 to n)                                          
         //Get value of element at that index (say val).
         //Check if array[val] is > 0 or not.
         if(array[ abs(array[i]) - 1] > 0)
                 //If it is greater than 0, multiply it with -1. In the beginning all the elements are array are
                 // positive. Multiplying it with -1 makes it negative and makes sure that the particular element is
                 //visited.
                 array [ abs(array[i]) - 1 ] =  array [ abs(array[i]) - 1 ] * -1;

         //Else do nothing.

// If a particular number occurs only once, its value at end of iteration should be negative.  If it occurs two times, the number number will be positive and that indicates that its duplicate.
Iterate through the array again. Find all the elements who's value if greater than 0.  Print those elements as  duplicates.

Java Implementation:

public class FindDuplicateInArrayWithGivenRange {

public void findDuplicates(int[] arr) {

for (int i = 0; i < arr.length; i++) {
if (arr[Math.abs(arr[i]) - 1] > 0)
arr[Math.abs(arr[i]) - 1] = arr[Math.abs(arr[i]) - 1] * -1;
}

for (int i = 0; i < arr.length; i++)
if (arr[i] > 0) {
System.out.print(arr[i] + " ");
}
}

public static void main(String args[]) {

int[] arr = { 1, 3, 4, 2, 5, 2, 3 };
new FindDuplicateInArrayWithGivenRange().findDuplicates(arr);
}
}


We iterate through the array two times so the run time is n + n = 2n = O(n).
As we don't need any extra space for our calculation, the space time is constant = O(1).