On Wed, May 26, 2010 at 06:01:15PM +0530, maverick.gugu wrote:
> How can we check for a cycle in this case? This is a cycle of 4 numbers..
> Can you please help in an algorithm to check for a cycle in n numbers..
> If i use recursion i wont be able to check the cycle rite?
I know of three different ways that can be used here.
One way is to record every number that you visit while executing the
algorithm. This requires keeping them in some kind of data structure,
so it takes some extra code. For every new number in the sequence, look
it up in the data structure. If you have visited that number before, then
the sequence will cycle from this point and never reach 1. You can now
mark all the number you have visited as 'unhappy'.
Another way is to keep track of how many steps you have taken in the
sequence, and remember the highest number you have visited so far.
If the number of steps is larger than that number, then you must have
repeated some numbers and you are in a cycle.
(For example, if you haven't seen a number larger than 17, and you
have taken 20 steps, then not all of those 20 steps could have been
unique numbers from 2 to 17. So there must have been repeating ones.
And if there are any repeating ones then you are in a cycle.)
A third way is the tail-chasing one. I can explain it better with
pseudocode:
function is_happy(n)
n1 = n
n2 = n
loop
n1 = step(n1)
n2 = step(step(n2))
return true if n2 == 1
return false if n2 == n1
end
end
(where step is the sum-of-squares-of-digits function)
Here you have two loop counters, a slow one which takes one step at
a time, and a fast one which takes two steps at a time. If the number
is happy then the fast one will get to 1 and we're done. (Note that
step(1) is always 1, so taking two steps at a time is not dangerous.)
If the number is not happy then n2 will go into a cycle, and at some
point n1 will enter the same cycle. Then it's just a matter of time
before n2 loops around the cycle and hits n1 from behind.
--
Richard Braakman
--
You received this message because you are subscribed to the Google Groups
"google-codejam" 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/google-code?hl=en.
