Find the single number that duplicates one or more times
Find the single number that duplicates one or more times in an array in O(1) space and O(n) time without modifying the array
Note:
You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n2).
There is only one duplicate number in the array, but it could be repeated more than once.
Note that, we can solve this problem by constructing a graph by considering each position as a vertex and value at an index as the pointer (or index) to the connecting vertex. In this way if there is no repeating element then the graph will be a simple non-cyclic path. But if there is repeating element then we will have cycles in the path. There is a very nice O(n) solution to find cycles in graphs.
Tortoise and Hair Cycle detection algorithm (pr Floyd's cycle-finding algorithm)
(From wiki)
Let S be any finite set, ƒ be any function from S to itself, and x0 be any element of S. For any i > 0, let xi = ƒ(xi−1). Let μ be the smallest index such that the value xμ reappears infinitely often within the sequence of values xi, and let λ (the loop length) be the smallest positive integer such that xμ = xλ+μ. The cycle detection problem is the task of finding λ and μ.
The figure shows a function ƒ that maps the set S = {0,1,2,3,4,5,6,7,8} to itself. If one starts from x0 = 2 and repeatedly applies ƒ, one sees the sequence of values
2, 0, 6, 3, 1, 6, 3, 1, 6, 3, 1, ….
The cycle in this value sequence is 6, 3, 1.
Floyd's cycle-finding algorithm, also called the "tortoise and the hare algorithm", alluding to Aesop's fable of The Tortoise and the Hare, is a pointer algorithm that uses only two pointers, which move through the sequence at different speeds.
The key insight in the algorithm is that, for any integers i ≥ μ and k ≥ 0, xi = xi + kλ, where λ is the length of the loop to be found and μ is the index of the first element of the cycle. In particular, whenever i = kλ ≥ μ, it follows that xi = x2i. Thus, the algorithm only needs to check for repeated values of this special form, one twice as far from the start of the sequence as the other, to find a period ν of a repetition that is a multiple of λ. Once ν is found, the algorithm retraces the sequence from its start to find the first repeated value xμ in the sequence, using the fact that λ divides ν and therefore that xμ = xμ + v. Finally, once the value of μ is known it is trivial to find the length λ of the shortest repeating cycle, by searching for the first position μ + λ for which xμ + λ = xμ.
The algorithm thus maintains two pointers into the given sequence, one (the tortoise) at xi, and the other (the hare) at x2i. At each step of the algorithm, it increases i by one, moving the tortoise one step forward and the hare two steps forward in the sequence, and then compares the sequence values at these two pointers. The smallest value of i > 0 for which the tortoise and hare point to equal values is the desired value ν.
Read full article from Find the single number that duplicates one or more times - Algorithms and Problem SolvingAlgorithms and Problem Solving
No comments:
Post a Comment