Find the Duplicate Number in an Array Without using Extra Space|Memory

Given an array of n+1 integers where each integer is between 1 and n (inclusive) . There is one duplicate number exist in this array. Write a code to find the duplicate number.

The array may or may not be sorted.

In this tutorial, i have discussed how we can solve this problem in O(n) time complexity without using any extra space/memory.

For example -

Example 1 -

In this example, the size of array is 4 and all the numbers in this array is between 1 and 3.

Input : {1, 3, 2, 2}
Output : 2


Example 2 -

Input : {3, 1, 3, 4, 2}
Output : 3

find the duplicate number leetcode,find duplicate in array interviewbit,find a duplicate number in an array,find a duplicate number in array,java,programming tutorials,interview questions,find duplicate number in an array without using extra memory,find duplicate number in an array in O(n) time complexity,