Stripe processes millions of payment transactions per day. A subtle bug in the idempotency layer caused certain transactions to be submitted twice, resulting in customers being double-charged. The transaction log is an array of N+1 integers where every integer is in the range [1..N] — meaning exactly one ID appears twice. The billing team has escalated this as a P0 incident.
Finance flagged that 3 customers were charged twice. The transaction log array has N+1 items in range [1..N], containing exactly one duplicate ID. Find it in O(n) time and O(1) space.
▶ Run Code to test against examples · Submit to judge all 5 test cases