Problem

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

OR

You are given an array of length n + 1 whose elements belong to the set {1, 2, ..., n}. By the pigeonhole principle, there must be a duplicate. Find it in linear time and space.

Examples

Example 1:

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

Example 2:

Input:
nums = [2,2,2,2,2]
Output:
 2

Constraints

  • 1 <= n <= 105
  • nums.length == n + 1
  • 1 <= nums[i] <= n
  • All the integers in nums appear only once except for precisely one integer which appears two or more times.

Follow Up

What if array modification is not allowed.

Solution

In this case, we don’t know how many times the duplicate occur, like we knew here - Find duplicate number in array with 1 to N+1 numbers with one number repeating. So, we can’t use that solution.

We can use hashset etc as standard answer. But lets solve in different way.

Method 1 - Modifying the Array with Negative Number

public int findDuplicate(int[] nums) {
	int len = nums.length;
	for (int num : nums) {
		int idx = Math.abs(num);
		if (nums[idx] < 0) {
			return idx;
		}
		nums[idx] = -nums[idx];
	}

	return len;
}

Time Complexity: O(n) Space Complexity: O(1)

Cons: Modifiying the array.

Method 2 - Using Linked List Cycle Approach i.e. Floyd Cycle Detection

This can be solved using Linked List Cycle 2 - Find Start of a Cycle, using fast and slow pointer.

The key is to understand how to treat the input array as a linked list.

Take the array [1,3,4,2] as an example, the index of this array is [0, 1, 2, 3], we can map the index to the nums[n].

0->1
1->3
2->4
3->2

Start from 0, use value nums[n] as a new index, and so on, until the index exceeds the bounds. This produces a sequence similar to a linked list.

0->1->3->2->4->null

If there are a repeated numbers in the array, take the array [1,3,4,2,2] as an example,

0->1
1->3
2->4
3->2
4->2

Similarly, a linked list is like that:

0->1->3->2->4->2->4->2->…

Here 2->4 is a cycle, then this linked list can be abstracted as the following figure:

With extra O(1) space, without modifying the input. Code: In this case slow and fast will be always in bound, and we need do while.

public int findDuplicate_fastSlow(int[] nums) {
	int slow = 0;
	int fast = 0;
	
	do {
		slow = nums[slow];
		fast = nums[nums[fast]];
	} while (slow != fast);

	slow = 0;
	while (slow != fast) {
		slow = nums[slow];
		fast = nums[fast];
	}
	
	return slow;
}

Source

https://leetcode.com/problems/find-the-duplicate-number/discuss/1892921/Java-9-Approaches-Count-%2B-Hash-%2B-Sort-%2B-Binary-Search-%2B-Bit-%2B-Fast-Slow-Pointers (56) Find the Duplicate Number - Floyd’s Cycle Detection - Leetcode 287 - Python - YouTube https://leetcode.com/problems/find-the-duplicate-number/

Other Sources

(204) Duplicate number in an immutable array | Floyd cycle detection algo | Leetcode #287 - YouTube

complete from: https://www.programcreek.com/2015/06/leetcode-find-the-duplicate-number-java/