Solutions

# Bit manipulation. Or sorting. Or set. Or negative marking. Or Floyd's algorithm.
# linked-lists

# Bit manipulation - O(n) time, O(1) space
def findDuplicate(nums: list[int]) -> int:
    res = 0 # to build the duplicate number bit by bit
    for b in range(32):
        mask = 1 << b

        # Count how many numbers in nums have this bit set
        bit_set = 0
        for n in nums:
            if n & mask:
                bit_set += 1

        # Count how many numbers between 1 and n-1 would have this bit set
        bit_set_exp = 0
        for i in range(1, len(nums)):
            if i & mask:
                bit_set_exp += 1

        # If the bit was set more time than expected,
        # it means the duplicate number has this bit set
        if bit_set > bit_set_exp:
            res |= mask
    return res


# Floyd's algorithm, slow and fast pointer: O(n) time, O(1) space
def findDuplicate5(nums: list[int]) -> int:
    slow, fast = 0, 0
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
    
    slow2 = 0
    while True:
        slow = nums[slow]
        slow2 = nums[slow2]
        if slow == slow2:
            return slow
    return -1

# Negative marking - O(n) time, O(1) space
def findDuplicate4(nums: list[int]) -> int:
    for i in nums:
        idx = abs(i) -1
        if nums[idx] < 0:
            return abs(nums[idx])
        nums[idx] *= -1
    return -1

# Sorting - O(n log n) time, O(1) space
def findDuplicate3(nums: list[int]) -> int:
    nums.sort()
    for i in range(len(nums)-1):
        if nums[i] == nums[i+1]:
            return nums[i]
    return -1

# Set - O(n) time, O(n) space
def findDuplicate2(nums: list[int]) -> int:
    seen = set()
    for i in nums:
        if i in seen:
            return i
        seen.add(i)
    return -1

# Brute force, double loop: O(n^2) time, O(1) space
def findDuplicate1(nums: list[int]) -> int:
    for i in range(len(nums)):
        cur = nums[i]
        for j in range(i+1, len(nums)):
            if cur == nums[j]:
                return cur
    return -1