Find the duplicate number

find_the_duplicate_number.py

"""
https://scammingthecodinginterview.com
Week 5: Two Pointer
Problem: 2
"""


class Solution(object):

    def solve(self, a):

        slow = a[0]
        fast = a[a[0]]

        while (slow != fast):

            slow = a[slow]
            fast = a[a[fast]]

        slow = 0

        while slow != fast:
            slow = a[slow]
            fast = a[fast]

        return slow


if __name__ == "__main__":
    a = [1, 2, 3, 4, 5, 1]
    ans = Solution().solve(a)
    print(ans)

This will break if the input array has anything but integers.

The naïve solution, with two for-loops, is more robust and simpler to read - but O(n²) time complexity:

a = [1, "a", 0, 3, None, 5, 6, 1, 7, 8, 9]

def find_duplicate(arr):
    for i, a in enumerate(arr):
        for j, b in enumerate(arr[i+1:]):
            if a == b:
                print(f"Duplicate found ({i}, {j+1})")

find_duplicate(a)