Find the Duplicate Number

Companies:
  • Amazon Interview Questions
  • Apple Interview Questions
  • Facebook Interview Questions
  • Google Interview Questions
  • Microsoft Interview Questions

Problem Statement

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Sample Test Case

Example 1:

Input: [1,3,4,2,2]
Output: 2
Example 2:

Input: [3,1,3,4,2]
Output: 3

Problem Solution

A very simple approach will be to first sort the entire array. If the numbers are sorted, then any duplicate numbers will be adjacent in the sorted array ,then we go on comparing each element to the previous element.

Because there is exactly one duplicate element in the array. We know that the array is of at least length 2, and we can return the duplicate element as soon as we find it.

Complexity Analysis

Time Complexity: The sort invocation takes O(nlogn) time which dominates the linear scan.

Space Complexity:O(1) Here, we sort nums in place, so the memory footprint is constant.

Code Implementation

#include<bits/stdc++.h>
using namespace std;

int findDuplicate(int nums[]) {
        sort(nums,nums+5);
        for (int i = 1; i < 5; i++) {
            if (nums[i] == nums[i-1]) {
                return nums[i];
            }
        }

        return -1;
    }


int main()
{
    int arr[5]={1,3,4,2,2};
    cout<<findDuplicate(arr);
}

 

Scroll to Top

Full Stack Integrated Bootcamp Free Trial

  • Please enter a number from 7000000000 to 9999999999.