Problem link: 3n + 1

Many thanks to Praveen and Prasad for bringing this problem back to me after many years. I had solved this problem long back and it had taken more than 3s initially (with AC of course!).

Prasad started to solve it again and I jumped in too. This time, I submitted 2 solutions:

1. Pre-compute the cycle length of all numbers [1,999999]. Read the inputs and print the outputs from the pre-computed array. Time = 0.442s.

2. I had suggested to Prasad to try and use the idea of computing the cycle length of a number just once. In the previous solution, we compute the cycle length of a number multiple times. I used a stack to keep track of the numbers and once I see a pre-computed cycle length for any number in the sequence, I just unwind the stack and set the cycle lengths for all numbers on the stack. Time = 0.062s.

Both the solutions use scanf, printf, & (bitwise and), >> (right shift), *=, +=.

Looks like the OJ (online judge) runs on really fast processors these days! The OJ upgrade is on :-)

One more spoiler: here's the source code :-) Am finally onto GitHub and it is befitting to add the source of the very first problem I solved years back and solved again due to Prasad.

One more spoiler: here's the source code :-) Am finally onto GitHub and it is befitting to add the source of the very first problem I solved years back and solved again due to Prasad.

Felt happy on reading my name :)

ReplyDelete:-) You and Alluri-gaaru brought this problem back again and so did Sai-gaaru. It is filled with fun to keep discussing the UVa problems. It is a pleasure to be associated with you guys.

ReplyDelete-raghav