A school assigns student roll numbers from 1 to n. However, its registration list contains n + 1 entries.

Exactly one roll number appears more than once. Every other roll number present in the list occurs only once.

Return the repeated roll number without changing the list and without using extra space that grows with the list size.

Method Signature

int findDuplicateRollNumber(List<Integer> rollNumbers)

Parameters

• rollNumbers: The roll numbers stored in the student registration list.

Returns

The only roll number that appears more than once.

Requirements

• Do not modify rollNumbers.
• Use only constant extra space.

Constraints

• 1 ≤ n ≤ 100,000
• rollNumbers.size() = n + 1
• 1 ≤ rollNumbers.get(i) ≤ n
• Exactly one roll number appears two or more times.
• Every other roll number present in the list appears exactly once.
• rollNumbers is never null.

Follow-Up Questions

1. Why is the list guaranteed to contain a repeated roll number?
2. Can you find the repeated roll number in linear time?

Examples

Example 1

findDuplicateRollNumber( rollNumbers = List.of(7, 3, 1, 6, 5, 2, 4, 5))

Returns 5.

Roll number 5 appears twice.

Example 2

findDuplicateRollNumber( rollNumbers = List.of(2, 4, 1, 3, 1))

Returns 1.

Roll number 1 is the only repeated roll number.

Example 3

findDuplicateRollNumber( rollNumbers = List.of(3, 3, 2, 3, 5, 1))

Returns 3.

Roll number 3 appears three times. A repeated roll number may occur more than twice.