Find Duplicate in Array Interviewbit Solution

illuminati
Sep 1, 2020
1 min read

Updated: Sep 8, 2020

Problem Description:

Given a read only array of n + 1 integers between 1 and n, find one number that repeats in linear time using less than O(n) space and traversing the stream sequentially O(1) times.

Sample Input:

[3 4 1 4 1]

Sample Output:

If there are multiple possible answers ( like in the sample case above ), output any one.

If there is no duplicate, output -1.

Solution:

Recent Posts

See All

Maximum Area of Triangle! InterviewBit Solution

Counting Triangles - InterviewBit Solution

You are given an array of N non-negative integers, A0, A1 ,…, AN-1.Considering each array element Ai as the edge length of some line segment

3 Sum Zero - InterviewBit Solution

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives

Comments

Maximum Area of Triangle! InterviewBit Solution

Given a character matrix of size N x M in the form of a string array A of size N where A[i] denotes ith row. Each character in the matrix co

Locking Unlocking of N-ary Tree

Given an n-ary tree of resources arranged hierarchically such that the height of the tree is O(log N) where N is a total number of nodes...

Counting Triangles - InterviewBit Solution

You are given an array of N non-negative integers, A0, A1 ,…, AN-1.Considering each array element Ai as the edge length of some line segment

3 Sum Zero - InterviewBit Solution

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives

3 Sum - InterviewBit Solution

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target.