Find duplicate in an array of N+1 Integers | 450DSA Python| Solved

 We are here solving Problem 450Dsa Find Duplicate Number into find duplicate in an array of N+1 Integers.

We are using Python 3 and some built-in function the arithmetic python is used.

Source :Leetcode

Problems:

 Find the Duplicate Number

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.

Solution:

class Solution:

    def findDuplicate(self, nums: List[int]) -> int:

        n = len(nums)

        # Validate input for correctness

        if n < 2 or min(nums) < 1 or max(nums) > n:

            raise ValueError("Invalid input: List size must be at least 2 and elements must be in the range [1, n]")

        slow = fast = 0  # Initialize pointers

        while True:

            slow = nums[slow]  # Move slow pointer one step

            fast = nums[nums[fast]]  # Move fast pointer two steps

            # If slow and fast pointers meet, a cycle is found, indicating a duplicate

            if slow == fast:

                break

        # Find the starting point of the cycle (duplicate)

        slow = 0

        while slow != fast:

            slow = nums[slow]

            fast = nums[fast]

        return slow

If You This Helped you Please Share this with others.