OJ Board

Hmm, if you use an array of (unsigned) chars instead of an array of 'booleans', you only need to initialise once in every 256 cases; not that it will save you much time, I think.

I agree with the previous posts that avoiding the extreme cases in the actual input for this problem, makes it misleading. The problem would be better off with a lower, but 'do-able in worst cases' limit. Unless, of course, there is an algo that needs less than O(N) function evaluations.

I used map<int,int> for this problem and get AC in 0.6 sec , i keep record of the time i was on a particular number, so when i found a number which was inserted in the map i found a cycle, so the length of the cycle is current_time - time_recorded_in_map

Hi,

Thanks to mf for mentioning the Floyd's Algorithm. It was really a nice algo and I have just got AC .. but the timing came really bad (about 4 sec). I had a few questions:

1. Well .. according to wiki .. I made two iterations and calculated the GCD to get the actual period. Is there any better way of doing it??

2. I used a stack (of integers) to evaluate the function. But is there any faster way???

Thnx in advance

I believe that floyd's algorithm is slower on this problem compared to the other algorithm.

Getting WA on this code:
Can't figure out where it's wrong, and example runs fine,
plus all i can think of, so looking for failed test-case.

Ecou wrote:Can't figure out where it's wrong, and example runs fine,
plus all i can think of, so looking for failed test-case.

Try the following input: The correct output is:

Thanks, fixed. I forgot to modulo after each operation.

PS: If you read this for testcases, the above is not like promised because of n > N.

Ecou wrote:Thanks, fixed. I forgot to modulo after each operation.

PS: If you read this for testcases, the above is not like promised because of n > N.

Ups, sorry I'll fix it.

And btw, please, remove your code after having accepted.