I think this is the algorithm you need...
i = 0;
j = 0;
do {
i = a[i];
j = a[a[j]];
} while i != j;
j = 0;
do {
i = a[i];
j = a[j];
} while i != j;
Then a[i] is the first repeated element and the algorithm complexity
is O(k).
See
http://en.wikipedia.org/wiki/Floyd%27s_cycle-finding_algorithm#Tortoise_and_hare
for an explanation of the algorithm. Notice that the array containing
the sequence is not altered and that the space complexity is O(1) as
only two integers are required for the implementation.
See also the problem in
http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/challenges/January2004.html,
and its solution in
http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/solutions/January2004.html.
Dave
On Jul 6, 8:59 am, sharad kumar <[email protected]> wrote:
> Given an array of n numbers in which all the members are less than or equal
> to k (k<n). device an algorithm of order O(k) to find the first repeating
> element
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
