That was a nice one. @Carlos: Thanks for the tip on dynamic programming; :-) DP is quite interesting: Memoization looks like a cool technique. It's just made the problem look so simple. But was just having a small doubt, is Memoization possible for all functions with recursion, where the function requires repeated calls?
Amtep: One couldn't have explained it better.. Its all getting clear now. :-) The 2nd method where you check for the number of steps with that number was really unique!! -Maverick On Thu, May 27, 2010 at 12:00 AM, Amtep <[email protected]> wrote: > 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]<google-code%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/google-code?hl=en. > > -- 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.
