Integer Replacement
Desicription
Given a positive integer n and you can do operations as follow:
 If n is even, replace n with n/2.
 If n is odd, you can replace n with either n + 1 or n  1.
What is the minimum number of replacements needed for n to become 1?
Example 1:
1 2 3 4 5 6 7 8
 Input: 8
Output: 3
Explanation: 8 > 4 > 2 > 1

Example 2:
1 2 3 4 5 6 7 8 9 10
 Input: 7
Output: 4
Explanation: 7 > 8 > 4 > 2 > 1 or 7 > 6 > 3 > 2 > 1

Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
 class Solution { private: std::unordered_map<long long , long long> map = std::unordered_map<long long, long long>{}; public: int integerReplacement(long long n) { if(n == 1) { return 0; }
if(map[n] == 0) { if(n & 1 == 1) { map[n] = 2 + std::min(integerReplacement((n + 1) / 2), integerReplacement((n  1) / 2)); } else { map[n] = 1 + integerReplacement(n / 2); } }
return map[n]; } };
