Technical Interview Question 1

You have an array of numbers from 0 to N-1, one of the numbers is removed, and replaced with a number already in the array which makes a duplicate of that number. How can we detect this duplicate in time O(N).

For example an array of 6 integers - 0,1,2,3,4,5. one of the number i.e "3" removed and replaced with "2". now array would become 0,1,2,2,4,5

Solution :

// InterviewQuestion1.java
public class InterviewQuestion1 {
   public static void main(String[] args) {
      int[] testArray = { 0, 1, 2, 2, 4, 5 };
      boolean[] testBool = new boolean[testArray.length];
      for (int i = 0; i < testArray.length; i++) {
         testBool[testArray[i]] = true;
      }
      System.out.print("Duplicate Number is : ");
      for (int i = 0; i < testArray.length; i++) {
        if (!testBool[i]) {
         System.out.print(testArray[i]);
         break;
        }
      }
   }
}

// Output: Duplicate Number is : 2