Find Duplicate in Array (InterviewBit)

#1

ques: https://www.interviewbit.com/problems/find-duplicate-in-array/

soln: https://ide.codingblocks.com/s/291725

how to handle this if there is no duplicate in the array, according to my code it may run infinite.

#2

@chaman9, yes your code does’nt handle that case ,let’s see the problem statement
Given a read only array of n + 1 integers between 1 and n, so from pigeonhole principle we can see that a number has to repeat there is no way it won’t be repeating as in that case you can’t fill n+1 space with n distinct number .
In case we have n elements , then what you can do for the case of no duplicate in the array, we can map each indexes to each numbers in this array. In other words, we can have a mapping function f(index) = number
For example, let’s assume
nums = [2,1,3] , then the mapping function is 0->2, 1->1, 2->3 .
If we start from index = 0, we can get a value according to this mapping function, and then we use this value as a new index and, again, we can get the other new value according to this new index. We repeat this process until the index exceeds the array. Actually, by doing so, we can get a sequence. Using the above example again, the sequence we get is 0->2->3 . (Because index=3 exceeds the array’s size, the sequence terminates!)

#3

If i am using extra space it is showing partially correct and telling to further optimise the code.
i tried unordered map and it was partial submission

so basically we have to do it in O(1) space

#4

the code you sent above is passing all cases in interviewbit, this question is intended to be solved without using extra space as using extra space will make this very easy that’s why you are getting partial marks , they want u to do it without using extra space

#5

yeaah my code is passing all test cases, feel like they have skipped one case

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.