Find the Duplicate Number - Python Solution Floyd's Algorithm Solution

 Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one duplicate number in nums, return this duplicate number.

Follow-ups:

  1. How can we prove that at least one duplicate number must exist in nums
  2. Can you solve the problem without modifying the array nums?
  3. Can you solve the problem using only constant, O(1) extra space?
  4. Can you solve the problem with runtime complexity less than O(n2)?

 

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [1,1]
Output: 1

Example 4:

Input: nums = [1,1,2]
Output: 1
class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        tortoise = hare = nums[0]
        while True:
            tortoise = nums[tortoise]
            hare = nums[nums[hare]]
            if hare == tortoise:
                break
        tortoise = nums[0]
        while tortoise !=hare:
            tortoise = nums[tortoise]
            hare = nums[hare]
        return tortoise
TC: O(N) SC: O(1)

No comments:

Post a Comment

Featured Post

H1B Visa Stamping at US Consulate

  H1B Visa Stamping at US Consulate If you are outside of the US, you need to apply for US Visa at a US Consulate or a US Embassy and get H1...