Collatz Conjecture, C++ (gcc)

Collatz Conjecture

//g++  5.4.0
/*
1 Collatz Conjecture
If a number is odd, the next transform is 3*n+1
If a number is even, the next transform is n/2
The number is finally transformed into 1.
The step is how many transforms needed for a number turned into 1.
Given an integer n, output the max steps of transform number in [1, n] into 1.
*/

#include <iostream>
#include <map> 
using namespace std;

class Solution{
public: 
    int maxStep(int n){
        int res = 0; 
        for(int i=0; i<=n; i++){
            res = max(res, findStep(i));
        }
        return res;
    }
    
private: 
        map<int,int> m; 
    int findStep(int n){
        if(n<=1) return 0; 
        if(m.count(n)) return m[n];
        int res; 
        if(n%2){//odd 
            res = 1 + findStep(3*n+1);
        }
        else{
            res = 1 + findStep(n/2); 
        }
        m[n] = res; 
        return res; 
    }
};

int main()
{
    Solution s; 
    cout << "1 -> " << s.maxStep(1) << endl;
    cout << "2 -> " << s.maxStep(2) << endl;
    cout << "7 -> " << s.maxStep(7) << endl; 
    
    return 0; 
}


run \| edit \| history \| help	0

λ

                                      .NET NoSQL database for rapid development