algoadvance

You are 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.

Example:

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

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

Clarifying Questions

1. Can nums contain negative numbers or zero?

   • No, each integer is in the range [1, n].

2. Is it guaranteed that there is exactly one duplicate number in the array?

   • Yes, it is guaranteed that there is only one repeated number.

3. Can I modify the input array?

   • No, the array should not be modified.

Strategy

We can use Floyd’s Tortoise and Hare (Cycle Detection) to solve this problem with O(n) time complexity and O(1) space complexity:

1. Phase 1: Detect Intersection Point:
   • Initialize two pointers: slow and fast.
   • Move slow by one step, and fast by two steps until they meet. This meeting point will be within the cycle.
2. Phase 2: Find the entrance to the cycle, which is the duplicate number:
   • Move slow to the start of the array and keep fast at the meeting point.
   • Move both pointers by one step until they meet again. This meeting point is the entrance to the cycle, i.e., the duplicate number.

Code

def findDuplicate(nums):
    # Phase 1: Detect Intersection Point
    slow = nums[0]
    fast = nums[0]
    
    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]
    
    return slow

Time Complexity

• Time Complexity: O(n) because each step through the loop takes constant time, and the number of steps is proportional to the size of the input array.
• Space Complexity: O(1) because we are using a fixed amount of extra space for the pointers slow and fast.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?