BinarySearch 0126 Detect the Only Duplicate in a List

Problem statement

https://binarysearch.com/problems/Detect-the-Only-Duplicate-in-a-List/

Solution

Equal to Leetcode 0287. Find the Duplicate Number.

Complexity

It is O(n) for time and O(1) for space.

Code

class Solution:
    def solve(self, nums):
        slow, fast = nums[0], nums[0]
        while True:
            slow, fast = nums[slow], nums[nums[fast]]
            if slow == fast: break
           
        slow = nums[0];
        while slow != fast:
            slow, fast = nums[slow], nums[fast]
        return slow