• Posted: 7 years ago
• 0 0
• Edit

Let us assume the input array is non negative. Since the input array can have duplicates there can be one or more than one element greater than the size of the input array. So there must be at least one element in between 0 and n-1 that is missing in the input array where n is the size of the input array. Hence, we can ignore the elements that are greater or equal to n . The algorithm works as :

• Iteration 1 : Iterate through the input array and write the value at the index to the index of the value recursively. Ignore all elements greater than n .
  
• Iteration 2 : Iterate through the input array once again to check whether there is a mismatch between the index and its value.
  
• If mismatch occurs, return the index.
  
• If not, return n .
  

public int findSmallestElemNotInAnArray(int[] array){

      /* Size of the array */
      int n = array.size;

      /* Iteration 1 */
      for (int i = 0; i  <  n; i++){
        currentValue = array[i];
        while(currentValue  <  n  & &  currentValue != array[currentValue]){
              nextValue = array[currentValue];
              array[currentValue] = currentValue;
              currentValue = nextValue;
        }
      }

      /* Iteration 2 */
      for (int i = 0; i  <  n; i++){
          if array[i] != i:
              return i;
              /* Since we are looking for the smallest element */
              break;
      }

      /* Otherwise */
      return n;

 }