Find the Duplicate Number Problem Statement

Given an integer array 'ARR' of size 'N' containing numbers from 0 to (N - 2). Each number appears at least once, and there is one number that appears twice. Your task is to find and return this duplicate number.

Example:

Input:

t = 1
N = 5
ARR = [0, 3, 1, 2, 3]

Output:

3

Explanation:

The number '3' is the duplicate because it appears twice in the array.

Constraints:

1

Question

Find the Duplicate Number Problem Statement

Given an integer array 'ARR' of size 'N' containing numbers from 0 to (N - 2). Each number appears at least once, and there is one number that appears twice. Your task is to find and return this duplicate number.

Example:

Input:

t = 1
N = 5
ARR = [0, 3, 1, 2, 3]

Output:

Explanation:

The number '3' is the duplicate because it appears twice in the array.

Constraints:

1 <= t <= 10^2
0 <= N <= 10^3
Time Limit: 1 sec

Note:

The duplicate number is always present in the given array.

Accepted Answer

Find the duplicate number in an array of integers from 0 to (N-2).

Iterate through the array and keep track of the frequency of each number using a hashmap.
Return the number with a frequency greater than 1 as the duplicate number.
Time complexity can be optimized to O(N) using Floyd's Tortoise and Hare algorithm.

Asked in Accenture