Find the Duplicate Number Problem (C++, Java, Python)

 

The array contains a lot of problems in the world of programming. One of the most interesting challenges is the identification of repeated numbers within an array. This article will discuss different approaches to finding the duplicate number present and implementing their code in C++, Java, and Python.

What is the Find the Duplicate Number Problem?

In the Find the Duplicate Number problem, we are given an array of integer nums containing n + 1 integers where each integer is inclusive in the range [1, n]. The array contains a duplicate number and our task is to return that duplicate number.

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

Output: 2

Brute Force Approach: Using Sorting

First, we will try to use the brute force approach, where we will use sorting to find the duplicate number. The initial step in this approach involves sorting the array in ascending order. After sorting duplicates numbers are adjacent to each other. So now we will simply compare the adjacent number using a loop.

Here are the steps involved in this approach:

• Sorting: first of all we will sort our array in ascending order using an inbuilt sort function

• Adjacent Comparison: After sorting the detection of duplicates becomes straightforward. By iterating through the array, a simple check of whether arr[i] is equal to arr[i+1] will tell us about the duplicate number.

The Time complexity is O(Nlogn + N) for this approach NlogN for sorting the array and O(N) for traversing through the array and checking if adjacent elements are equal. The Space complexity is O(1) as we are not using any extra space.

Better Approach: Using a Frequency Array

In this approach, we will create a frequency array of size N+1. and now we will set all elements of the frequency array to 0. The following are the steps used in this approach:

• Now we will iterate through each element in the given array. Check the corresponding index in the frequency array.
• Now if the frequency of the element is 0 we will increase it by 1, else if the frequency is not 0 then that element is the duplicate element.

The time complexity is O(N) as we traverse through the array only once. The space complexity is O(N) as we use extra space for the frequency array.

Optimal Approach: Using Linked List Cycle

If there is a duplicate number we can always say that a cycle will be formed. This approach utilizes Floyd’s Tortoise and Hare algorithm commonly used for cycle detection in linked lists.  In a cycle, the distance traveled by the fast pointer is twice that of the slow pointer.

If you don’t know much about Floyd’s Tortoise and Hare algorithm, you can learn more about linked list cycle detection.

Following are the steps involved in finding the duplicate number using the linked list cycle:

• Initially, we have 1, then we got to the first index, we have 4,
• we go to the 4th index, we have 2, 
• we go to the 2nd index, we have 3, 
• we go to the 3rd index, we get 2 again, and here the cycle is formed.

• We will consider each index in the array as a node in a linked list and initialize two pointers, slow and fast, both pointing to the first element of the array.

• Now we will use a loop to move the slow pointer one step at a time and the fast pointer two steps at a time.

• If there is a duplicate in the array, the pointers will eventually meet at the same index, forming a cycle.

• Once the slow and fast pointers meet, reset one of the pointers (let’s say slow) to the first element

• Now we will move both pointers one step at a time until they meet again. The meeting point is the entrance to the cycle

• The element at the entrance to the cycle is the duplicate number in the array.

C++ Code

We provided the C++ program to find the duplicate number:

#include <bits/stdc++.h>

using namespace std;

// Function to find the duplicate number in an array using linked list cycle detection
int findDuplicate(vector<int> &nums) {
    int slow = nums[0];
    int fast = nums[0];

    // Phase 1: Detect the intersection point in the cycle
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);

    // Phase 2: Find the entrance to the cycle
    slow = nums[0];
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }

    // The duplicate element is found at the entrance to the cycle
    return slow;
}

int main() {
    // Example usage with the array [1, 4, 3, 2, 2]
    vector<int> nums = {1, 4, 3, 2, 2};
    
    // Call the findDuplicate function and display the result
    cout << "The duplicate element is " << findDuplicate(nums) << endl;

    return 0;
}

Java Code

Here is the Java program for this leetcode problem:

import java.util.Arrays;

public class FindDuplicate {

    // Function to find the duplicate number in an array using linked list cycle detection
    public static int findDuplicate(int[] nums) {
        int slow = nums[0];
        int fast = nums[0];

        // Phase 1: Detect the intersection point in the cycle
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        // Phase 2: Find the entrance to the cycle
        slow = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }

        // The duplicate element is found at the entrance to the cycle
        return slow;
    }

    public static void main(String[] args) {
        // Example usage with the array [1, 4, 3, 2, 2]
        int[] nums = {1, 4, 3, 2, 2};
        
        // Call the findDuplicate function and display the result
        System.out.println("The duplicate element is " + findDuplicate(nums));
    }
}

Python Code

You can implement it in Python as well:

def findDuplicate(nums):
    slow = nums[0]
    fast = nums[0]

    # Phase 1: Detect the intersection point in the cycle
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break

    # Phase 2: Find the entrance to the cycle
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]

    # The duplicate element is found at the entrance to the cycle
    return slow

# Example usage with the array [1, 4, 3, 2, 2]
nums = [1, 4, 3, 2, 2]
print("The duplicate element is", findDuplicate(nums))

Output:

The duplicate element is 2

The time complexity is O(N) as we traverse through the array only once. The space complexity of this approach is O(1) as we haven’t used any extra space.

In the end, let’s do a comparative analysis of all the methods:

Conclusion

In conclusion, we explored three approaches to solve this leetcode problem of identifying the duplicate number in an array: the Sorting Approach, the Frequency Approach, and the optimal Linked List Cycle Detection. The Linked List Cycle Detection stands out with linear time complexity and minimal space usage, making it the optimal choice.