7. Find Duplicate Number

You’re interviewing for a backend or data engineering role at a FAANG-level company. The interviewer describes a real product scenario:

A large-scale analytics platform ingests event IDs generated by multiple distributed services. Due to a synchronization issue, exactly one event ID is accidentally generated more than once.

The system stores all incoming event IDs in an integer array nums.
Each event ID should be unique, but one ID appears multiple times.

The platform needs a fast and memory-efficient way to identify the duplicated event ID without modifying the original data, since the array may be used by other services.

This is a common coding interview and DSA question might ask in Google, Amazon, Netflix, Meta, Apple, Microsoft, Uber, and Bloomberg interviews.

Your Task

Given an integer array nums containing n + 1 integers where:

• Each integer is in the range 1 to n inclusive
• There is exactly one duplicated number

Return the duplicated number.

Input Format

• nums: an array of integers of size n + 1

Output Format

• A single integer representing the duplicated number

Examples

Constraints

• 1 <= n <= 100,000
• nums.length == n + 1
• 1 <= nums[i] <= n
• Exactly one number is duplicated
• The array must not be modified
• Use only constant extra space if possible