"""Find a duplicate in an array of n+1 integers each in [1, n].

Classic Floyd's tortoise-and-hare on the implicit linked list defined by
f(i) = nums[i]. Guarantees O(n) time, O(1) extra space, and does not
mutate the input. Returns a duplicated value; when several values repeat,
returns one of them (the entry point of the cycle reachable from index 0).

Edge cases handled:
  - len(nums) < 2  -> ValueError
  - values out of [1, n], or not a plain int (bool and float included)
                    -> ValueError
  - no duplicate present  -> unreachable, and therefore never raised:
    a no-duplicate array cannot satisfy both preconditions at once. With
    len(nums) = n + 1 values drawn from 1..n, pigeonhole forces a repeat;
    the only arrays that avoid one are shorter than n + 1 or carry a value
    outside 1..n, and both are refused by the gates above before Floyd
    runs (see `_no_duplicate_guard()`). The count check after phase 2 is
    kept as an invariant, not as a handler: an entry node has two distinct
    predecessors by definition, so its value occurs at least twice.
"""
from typing import List


def _no_duplicate_guard(candidate: int, nums: List[int]) -> int:
    """Invariant: the phase-2 entrance value is duplicated, or raise.

    Unreachable on validated input (see the module docstring). It is here so
    that an edit which widens the gates above -- or shortens phase 2, the other
    half of the argument -- fails loudly instead of returning a value as if it
    were a duplicate. Measured: the raise fires 0 times over every validated
    input for n = 1..4, and it *does* fire when phase 2's loop is deleted, which
    is the edit it exists for. `test_find_duplicate.py` pins that this is the
    module's only unexecuted line, so removing it, or growing new dead code
    beside it, moves a cell.
    """
    if nums.count(candidate) < 2:
        raise ValueError("no duplicate present in nums")
    return candidate


def find_duplicate(nums: List[int]) -> int:
    n = len(nums) - 1
    if n < 1:
        raise ValueError("nums must contain at least 2 elements")
    for v in nums:
        if not isinstance(v, int) or isinstance(v, bool) or v < 1 or v > n:
            raise ValueError(f"value {v!r} out of range [1, {n}]")

    # Phase 1: find meeting point inside the cycle.
    slow = nums[0]
    fast = nums[nums[0]]
    while slow != fast:
        slow = nums[slow]
        fast = nums[nums[fast]]

    # Phase 2: find cycle entrance = duplicate.
    slow2 = 0
    while slow2 != slow:
        slow2 = nums[slow2]
        slow = nums[slow]
    # Floyd alone would return an entrance value even for a permutation; the
    # guard below states the invariant that the range gates make that
    # impossible. It is a proof checkpoint, not a scenario handler.
    return _no_duplicate_guard(slow, nums)


def _self_test() -> None:
    import random

    # Known duplicates.
    cases = [
        ([1, 3, 4, 2, 2], 2),
        ([3, 1, 3, 4, 2], 3),
        ([1, 1], 1),
        ([2, 2, 2], 2),  # value appearing 3x still reports 2
        ([1, 2, 3, 4, 5, 5], 5),
    ]
    for nums, expected in cases:
        got = find_duplicate(nums)
        assert got == expected, (nums, got, expected)

    # Randomized: inject one duplicate into a permutation.
    rng = random.Random(42)
    for trial in range(200):
        n = rng.randint(1, 40)
        base = list(range(1, n + 1))
        dup = rng.randint(1, n)
        base.append(dup)
        rng.shuffle(base)
        assert find_duplicate(base) == dup, (base, dup)

    # Input must not be mutated.
    original = [1, 3, 4, 2, 2]
    snapshot = list(original)
    find_duplicate(original)
    assert original == snapshot

    # Error cases.
    for bad in ([], [1], [0, 1], [1, 3], [1, 2, 3, 4], [True, 1]):
        try:
            find_duplicate(bad)
        except ValueError:
            pass
        else:
            raise AssertionError(f"expected ValueError for {bad!r}")

    # The no-duplicate case never reaches Floyd: a permutation of 1..n has
    # length n, which is one short of a valid input, so the range gate
    # refuses it with an out-of-range message. The `no duplicate present`
    # branch cannot fire on any validated input -- pinned as the module's
    # only unexecuted line in test_find_duplicate.py.
    for permutation in ([1, 2, 3, 4], [2, 1], [1, 2, 3]):
        try:
            find_duplicate(list(permutation))
        except ValueError as exc:
            assert "out of range" in str(exc), (permutation, exc)
        else:
            raise AssertionError(f"expected ValueError for {permutation!r}")

    print("ALL TESTS PASSED")


if __name__ == "__main__":
    _self_test()