Problem Statement
You have an array A containing N elements. Out of these N elements, there are N-1 unique elements and exactly one element is duplicated. Your task is to find and print the duplicate element in the array.
Approach
To find the duplicate element efficiently, we can use a tracking array called Hash. Here’s a step-by-step breakdown of the approach:
-
Initialize a Tracking Array: Create an array Hash of size MX (in this case, 10001) to keep track of the occurrences of each element in the array A. This array will help us count how many times each number appears.
-
Iterate Through the Array: Loop through each element in the array A. For each element a[i], do the following:
-
Check if Hash[a[i]] is greater than 0. If it is, this means we have seen this element before, so it is the duplicate. We print this element and break out of the loop.
-
If Hash[a[i]] is 0, it means this is the first time we are encountering the element. We increment Hash[a[i]] by 1 to record its occurrence.
-
This approach ensures that we efficiently identify the duplicate by leveraging the counting mechanism of the Hash array.
Time Complexity
- O(N): The time complexity is linear, as you only loop through the array once.
Space Complexity
- O(MX): The space complexity is constant, determined by the size of the Hash array.