Home/

...

/

Find the Duplicate Number (easy)

Find the Duplicate Number (easy)

Problem Statement

We are given an unsorted array containing ‘n+1’ numbers taken from the range 1 to ‘n’. The array has only one duplicate but it can be repeated multiple times. Find that duplicate number without using any extra space. You are, however, allowed to modify the input array.

Example 1:

Input: [1, 4, 4, 3, 2]
Output: 4

Example 2:

Input: [2, 1, 3, 3, 5, 4]
Output: 3

Example 3:

Input: [2, 4, 1, 4, 4]
Output: 4

Try it yourself

Try solving this question here:

class FindDuplicate {
  public static int findNumber(int[] nums) {
    // TODO: Write your code here
    return -1;
  }
}

Solution

This problem follows the Cyclic Sort pattern and shares similarities with Find the Missing Number. Following a similar approach, we will try to place each ...