We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Practice
  • Certification
  • Compete
  • Career Fair
  • Hiring developers?
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #14: Longest Collatz sequence
  4. Discussions

Project Euler #14: Longest Collatz sequence

Problem
Submissions
Leaderboard
Discussions

Sort 186 Discussions, By:

votes

Please Login in order to post a comment

  • GiorgianB 6 years ago+ 0 comments

    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.

    19|
    Permalink
  • Tashaion 3 years ago+ 0 comments

    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;
    }
    
    12|
    Permalink
  • sean_wlx 3 years ago+ 0 comments

    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.
    9|
    Permalink
  • luka_null 5 years ago+ 0 comments

    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.

    6|
    Permalink
  • c650Alpha 4 years ago+ 0 comments

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

    5|
    Permalink
Load more conversations

Need Help?


View top submissions
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature