Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
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
Variadic template example
mergesort tree
FAK MEN
Example Iterator Increment
Such case
Dar
stack::emplace for 30-second c++
ApelRefVal
HashTable
Vectores - insertar ordenado e imprimir