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;
}

Complexity

  • ⏰ 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. In this case slow and fast will be always in bound, and we need do while.

Code

Java
public class Solution {
    public int findDuplicate(int[] nums) {
        // Initialize two pointers, slow and fast
        int slow = 0;
        int fast = 0;
        
        // Use a do-while loop to move the pointers in the cycle
        // Move slow pointer one step at a time
        // Move fast pointer two steps at a time
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast); // Continue until they meet
        
        // Reset the slow pointer to the start
        slow = 0;
        
        // Move both pointers one step at a time until they meet again
        // The meeting point is the duplicate number
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        
        // Return the duplicate number
        return slow;
    }
}
Python
class Solution:
    def findDuplicate(self, nums: list[int]) -> int:
        # Initialize two pointers, slow and fast
        slow = 0
        fast = 0
        
        # Use a while loop to move the pointers in the cycle
        # Move slow pointer one step at a time
        # Move fast pointer two steps at a time
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            # Continue until they meet
            if slow == fast:
                break
        
        # Reset the slow pointer to the start
        slow = 0
        
        # Move both pointers one step at a time until they meet again
        # The meeting point is the duplicate number
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]
        
        # Return the duplicate number
        return slow

Complexity

  • ⏰ Time complexity: O(n), since each pointer only traverses the array a limited number of times.
  • 🧺 Space complexity: O(1) as only a few extra variables (pointers) are used.

Method 3 - Using Xor

The XOR approach leverages the properties of the XOR operation:

  1. Properties of XOR:

    • A XOR A = 0.
    • A XOR 0 = A.
    • XOR is both commutative and associative, meaning the order of operations does not matter.

  2. Approach:

    • XOR all the elements in the array.
    • XOR the result with all integers from 1 to n.
    • Due to the properties of XOR, all elements that appear twice will cancel out, and the result will be the duplicate number.

Code

Java
public class Solution {
    public int findDuplicate(int[] nums) {
        int n = nums.length - 1;
        int xorResult = 0;

        // XOR all array elements
        for (int num : nums) {
            xorResult ^= num;
        }

        // XOR with all numbers from 1 to n
        for (int i = 1; i <= n; i++) {
            xorResult ^= i;
        }

        return xorResult;
    }
}
Python
class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        n = len(nums) - 1
        xor_result = 0

        # XOR all array elements
        for num in nums:
            xor_result ^= num

        # XOR with all numbers from 1 to n
        for i in range(1, n + 1):
            xor_result ^= i

        return xor_result

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)