🚀Day 12/180 (Math) 287. Find the Duplicate Number(Leetcode)

Find the Duplicate Number

#180DaysOfDSA#DailyCodingChallenge #LeetCodeJourney #GeeksforGeeks #CodingNinjas #Codechef #CodeForces #ContinuousLearning #TechCommunity

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = nums[0];
        int fast = nums[0];

        while (true) {
            slow = nums[slow];
            fast = nums[nums[fast]];

            if (slow == fast) {
                break;
            }
        }

        int slow2 = nums[0];

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

        return slow;        
    }
}

This Java class provides a solution to the problem of finding a duplicate number in an array using Floyd's Tortoise and Hare algorithm (cycle detection). Here is a summary of the key points:

• Initialization: Two pointers, slow and fast, are initialized to the first element of the array.

• Cycle Detection:

  • The slow pointer moves one step at a time (slow = nums[slow]).

  • The fast pointer moves two steps at a time (fast = nums[nums[fast]]).

  • The loop continues until slow and fast pointers meet, indicating a cycle.

• Finding Entrance to Cycle:

  • A new pointer slow2 is initialized to the first element.

  • Both slow and slow2 move one step at a time until they meet.

  • The meeting point is the duplicate number in the array.

• Return Value: The function returns the duplicate number.