Thanks for this problem. Is was very interesting, and taught me the value of caching and meomization. Also learned some techique about it while doing so.Thanks shashank21j.

Some Hints To Solve This :-

1. Use MEMOIZATION.
2. Recursion can be Super-Useful.
3. Take care of special-cases:- i.)if x=x*3+1 ,for cache[x] x>5000001 it can be error or deadlock,because we declared cache[5000001] only

4. At last to find max result ,use memoization too ,means store the result already.

   i am giving my solution ,which passed all test cases successfully.......

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ulli;
typedef signed long long int lli;

ulli *arr=new ulli[5000001];
	
ulli countchain(ulli num)
{
	ulli temp=0;
//	cout<<num<<" : "<<arr[num]<<endl;
	if(arr[num]!=0)
	{
		return arr[num];
	}
	if(num%2==0)
	{
		temp=num/2;
		arr[num]=1+countchain(temp);
		return arr[num];
	}
	temp=num*3+1;
	ulli count=1;
	while(temp>5000001)
	{
		
		
		if(temp%2==0)
		{
			temp/=2;
		}
		else
		{
			temp=temp*3+1;
		}
		count++;
	}
	arr[num]=count+countchain(temp);
	return arr[num];
	
}
int main()
{
 	
 		memset(arr,0,sizeof(arr));
 		ulli count=0;
 		arr[1]=1;
 		for(ulli a=2;a<=5000001;a=a*2)
 		{			
 			++count;
 			arr[a]=count;			
		}
		for(ulli a=1;a<=5000001;++a)
		{
			//cout<<a<<" : "<<countchain(a)<<endl;
			countchain(a);
		}
	
		ulli *results=new ulli[5000001];
		results[1]=1;
		for(ulli a=2;a<=5000001;++a)
		{
			if(arr[a]>=arr[results[a-1]])
			{
				results[a]=a;
			}
			else
			{
				results[a]=results[a-1];
			}
		}
		ulli test_case=0;
		cin>>test_case;
		ulli end_number,max_answer=0,result=0;
		while(test_case--)
		{
			cin>>end_number;
			cout<<results[end_number]<<endl;
			
		}
		delete[] results;
		delete[] arr;	
 	   return 0;
}

Finally passed all tests with my Python3 implementation without timing out. Some lessons learned:

• Casting is very expensive, so instead of doing divide + cast to int, try doing shift
• Python dictionaries are insanely expensive compared to lists
• Lists are expensive compared to storing state in the framestack, aka recursion
• Getting fancy with pre-computing low-hanging fruit results usually doesn't pay off, just keep it simple. Exhaustive search with memoization is fast enough.

Thought I did it well. And then I saw the Editorial.

Did anyone solve this in Python3? I spend 2 hours trying to optimize the code, but I still get a timeout during memoization. Same code in Java runs in under 1s.

Been banging my heads against this one for a while, and I've just completely run out of ideas for ways to increase the efficiency. I'm working in python 2. I would love if someone could take a look at this submission and perhaps nudge me towards a better solution. https://www.hackerrank.com/contests/projecteuler/challenges/euler014/submissions/code/2416055

I am getting case 0 to 4 proper, but case 5 to 8 are returned as wrong answer and remaining cases goes for time out. https://www.hackerrank.com/contests/projecteuler/challenges/euler014/submissions/code/1301211928

Lesson learned: Caching is important for speed but don't cache everything. A naive approach is to use a built-in cache like "lru_cache" or set up your own cache using a dictionary to store everything. But there are too many numbers to cache; I kept track of the highest number occuring in a Collatz sequence after running N up to 5x10^6: 1318802294932. That number and other high numbers will likely never be called once they are cached. Set the cache to only store lengths for numbers less than 5 million or so. If a number is less than your chosen cache size then don't store it. Then, because your cache size is set, use a list instead of a dictionary to save space. I used Python 3.

I wonder how it is possible to perform all calculations in runtime using Python. I copied the code from Editorial and it runs on my machine for more than 1 minute to finish all calculations. My own solution can obtain the same results in 20 seconds, but it's still too slow for submission. If it is TopCoder or Google Code Jam it would be disastrous.

Sorry for asking old topic but does anyone finish this challenge by ruby? I can't finish when set the max number is 5*10^6, seem like the speed of ruby is not enough :( this is my code, please help me find out :(

# Enter your code here. Read input from STDIN. Print output to STDOUT
t = gets.strip.to_i
def steps n
    start = 0
    loop do
        break if n == 1
        if n % 2 == 0 
            n = n / 2
        else
            n = 3*n + 1
        end
        start += 1
    end
    start
end
numbers = [1,1,2]
max = 5000000
current_number = 2
current_step = 1
(3..max).each do |number|
    p number
    step = steps(number)
    if step >= current_step
        current_number = number
        current_step = step
    end
    numbers << current_number
end
t.times do |time|
    n = gets.strip.to_i
    p numbers[n]
end