Given that array is of range 1..n and of n+1 length. Atleast one is repeated - so number of unique integers is (n -1 + 1) = n
E.g [3, 4, 6, 5, 4, 4, 2] -> length is 7 so range has to be 1..6 ; no of possible unique integers is (6-1 +1 = 6)
The number of elements is always one greater than the number of unique possibilities.
If we cut this in half - the condition should still hold true - so atleast one of those halves should have one more element that the number of unique possibilities.
If the half you have chosen, does not have more elements than the number of unque possibilities, drop that half.
If the half you have chosen, meets the condition, then cut it into two again.
Repeat cutting in halves until you are left with just one item.
The problem asked for space efficiency, so we are doing this in-place without creating another array.
It has O[1] space, and O[logn] time as we used binary search (cutting in halves).
Used a version of binary search to do this..
Logic:
The problem asked for space efficiency, so we are doing this in-place without creating another array.
It has O[1] space, and O[logn] time as we used binary search (cutting in halves).
Note - there is a better way to improve this and reduce time to O[n]