You may store the number in a set, and check if the number is already in the
set or not. I don't know if this is fast enough for the large set but
probably is for the small.
To speed it up you can use some cache, in your example you can be sure that
14, 17, 23, 13, 16, 37, 52, 29 and 41 are not happy in base 7 since they all
lead to the same cycle. So if you know some number x is not happy in a
particular base B, and a number y produces x at one step, then y isn't happy
either in base B.
I used a dynamic programming with memoization like function that tells
whether a number "n" is happy in base "base", something this.
bool happy[MAX][11];
bool known[MAX][11];
bool cycle[MAX][11];
bool IsHappy(int n, int base) {
if ( n == 1 ) return true; // is happy
if ( known[n][base] ) return happy[n][base]; // result is in cache
if ( cycle[n][base] ) return false; // hit a cycle
cycle[n][base] = true; // mark it as having a cycle
happy[n][base] = IsHappy(GetNext(n, base), base); // find whether the
next number is happy or not
known[n][base] = true; // now I know the result for "n" in base "base"
return happy[n][base];
}
I used 20000000 for MAX, I don't remember how I got this number.
You can read about dynamic programming and memoization here:
http://www.topcoder.com/tc?module=Static&d1=features&d2=040104
Carlos Guía
On Wed, May 26, 2010 at 8:31 AM, maverick.gugu <[email protected]>wrote:
> For instance:
> In the case of 11 base 7:
> 11 base 7 = 14
> *1^2 + 4^2 = 17*
> 17 base 7 = 23
> 2^2 + 3^2 = 13
> 13 base 7 = 16
> 1^2 + 6^2 = 37
> 37 base 7 = 52
> 5^2 + 2^2 = 29
> 29 base 7 = 41
> *4^2 + 1^2 = 17*
> .....
>
> 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?
>
> 2 conditions to be checked:
> 1. cycle of n numbers
> 2. if sum is 1
>
>
> thanks,
> Maverick
>
> --
> 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.
