Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is in the range [1, n], prove that there is only one duplicate number in the array. Return this duplicate number.

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

Sample Input and Expected Output:

Input:

nums = [1, 3, 4, 2, 2]

Output:

The duplicate number is: 2

Input:

nums = [3, 1, 3, 4, 2]

Output:

The duplicate number is: 3

Solution in C++:

The problem can be solved using the “Floyd’s Tortoise and Hare” algorithm (Cycle Detection algorithm). The idea is to consider the array as a linked list where each element nums[i] points to the element at index nums[i]. Since there is a duplicate number, there will be a cycle in the linked list. We use two pointers, slow and fast, to traverse the list. The slow pointer moves one step at a time, and the fast pointer moves two steps at a time. If there is a cycle, they will eventually meet inside the cycle.

Once the meeting point is found, we reset one of the pointers to the beginning of the array and move both pointers one step at a time. The meeting point is the start of the cycle, which corresponds to the duplicate number.

#include <iostream>
#include <vector>

int findDuplicate(std::vector<int>& nums) {
    // Phase 1: Find the meeting point of the two pointers (Floyd's Tortoise and Hare algorithm).
    int slow = nums[0];
    int fast = nums[0];

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

    // Phase 2: Find the start of the cycle (duplicate number).
    slow = nums[0];
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }

    return slow;
}

int main() {
    std::vector<int> nums1 = {1, 3, 4, 2, 2};
    std::vector<int> nums2 = {3, 1, 3, 4, 2};

    int result1 = findDuplicate(nums1);
    int result2 = findDuplicate(nums2);

    std::cout << "The duplicate number is: " << result1 << std::endl;
    std::cout << "The duplicate number is: " << result2 << std::endl;

    return 0;
}

Time Complexity and Space Complexity:

The time complexity of the solution is O(n), where n is the size of the input vector nums. The “Floyd’s Tortoise and Hare” algorithm guarantees that the two pointers will meet after traversing at most 2n steps. Since each pointer moves at most n steps, the time complexity is linear with respect to the size of the input array.

The space complexity is O(1) as we are using a constant amount of additional space for variables in the solution, regardless of the size of the input array. The algorithm is performed in-place without using any extra data structures.