Find duplicate number in array In O(n) time and O(1) space

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 in O(n) time and O(1) space

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 can 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. However, this approach takes O(nlogn) time and is not a suitable approach.

Since the problem states to find the duplicate number in O(n) time and O(1) space, we can use a simple property to do the same.

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
[gravityforms id="5" description="false" titla="false" ajax="true"]