Finding duplicate element in infinite array

[yuwaraj]

hi,
An array has infinite elements in which first 'n' elements are integers and rest are '-infinity' and among 'n' element only
one is repeated rest are distinct and i hv to find that duplicate element.
First thing how do i find value of 'n' then if i had it how do i find that duplicate element ( please do not suggest linear search) .

ex.: [ 2,8,3,5,6,9,6,1,4,7,-inf,-inf,...........,-inf]

where -inf is -infinity and duplicate element is '6'

thanx in advance

[Yves M]

How is the array encoded in your program? Which programming language are you using?

[MrViggy]

Can you do this in a non-linear fashion? The array looks like it's not sorted, and you don't know what the repeated element is. I suppose if you sorted the array first, then did a search for each element.



Viggy

[cma]

If the obvious quadratic algorithm for finding the duplicate is not acceptable, and you're doing this in Java, then here's a solution, create a HashSet and add each element in the array into the set, if the add() method returns false, you've found your duplicate (some C++ set implementation may have something similiar, where the return value is a pair which stores an iterator to the element added into the set and a bool value indicating whether insertion was possible, whether a duplicate was found). The total size of the set will be your value of n (assuming you keep adding even after finding the duplicate until you find the infinity/sentinel value). Running-time is linear, unless you decide to use a TreeSet, which then becomes O(n*log(n)). Alternatively, (and this would probably work with any programming language you're using), create a map, with the keys as each values of the elements in the array and the key's associated value as the number of times that value is seen in the array, this solution would work better if there were 3+ repeated elements in the array.

[MrViggy]

In C++, one could use a std::set.

Heh! I was focused on the array, not thinking that one could just insert the elements into a set!!!



Viggy

[cma]

That is another solution (imo just as acceptable as using a set), sort the array using an efficient (fast) algo. (merge-sort, quick-sort, w/e), then do an adjacent comparison, checking if elem[0] == elem[1], if true, duplicate found, else, compare if elem[1] == elem[2], etc. Running time is O(n*log(n)).

[yuwaraj]

Hi all,
First of all thanx for so many replies.
See as in this is question for one of my interview ,and in this problem no such language is specified .
Ya surely we can sort an array and check previous and the next ( i and i+1 ) element's for equality but what confuses me most
is this is infinite array and we don't know the value of 'n' which are integers ( rest (minus) -infinity).And if i have to
sort i hv to sort in descending order otherwise '-infinity' will come before rest ('n') integers.
Otherway we can hv extra space(array 'arr') as large as array size we can index each element in this array ( eg. 2 will go to index
arr[2]) and if element is duplicate then , when it'll come next time the position will be occupied allready. But what if we don't hv an extra
space.
Can we hv solution for constant space and constant order ( not function of 'n')?

Waiting for reply....

[Yves M]

Ok, first of all, an infinite array can't be encoded as a regular array in a programming language. No computer has infinite memory. This means that as the problem is presented, you probably have a means of knowing 'n' directly, since one sensible encoding would be array[1..n] where the -inf elements are only implicit. Since array[1..n] is not sorted, you can't solve this problem in less time than O(N), because you have to look at each element at least once in the worst case. So constant time is impossible, unless you have full control of how the data is encoded. Constant space can easily be achieved by sorting, which would then be O(N log(N)).

[cma]

What? Sorting doesn't entail extra space (depending on the algorithm used). From the look's of it, this "infinite" array is just an abstraction of only looking at part of the array. All they really mean is, here's an array, one half of the array stores the important data, the other half contains data that can be ignored, how would you work on it? Using my solution with the set, would get you O(n) (if you used a hash set, using a set that keeps its elements sorted would get you O(n*log(n)), n adds each costing log(n) time), but if you can't use any extra space what-so-ever, then sorting the array and then doing the adjacent comparison's would get you O(n*log(n)) which isn't too bad ( O(n*log(n)) for sort, and then O(n) for the search get's you order n*log(n))

[RoboTact]

If there is no limit for value of element, the most effitient solution would be hash set... It entails in O(n*log(n)) time, more specific O(n*log(n/m)) time and O(n+m) memory (whitch is literally the same, but closer to the numerical order) where m is the size of hash table.