func findDuplicate(nums []int) int {
    slow := nums[0]
    fast := nums[nums[0]]
    
    for slow != fast {
        slow = nums[slow]
        fast = nums[nums[fast]]
    }
    
    slow2 := 0
    
    for slow != slow2 {
        slow = nums[slow]
        slow2 = nums[slow2]
    }
    
    return slow
}

func findDuplicate(nums []int) int {
    left := 1
    right := len(nums) - 1
    
    for left < right  {
        mid := left + (right - left) / 2
        
        sum := 0
        for i:=0; i<len(nums); i++ {
            if nums[i] <= mid {
                sum +=1
            }
        }
        
        if sum > mid {
            right = mid
        } else {
            left = mid + 1
        }
    }
    
    return left
}