### 700

The 700th LC problem that I solved reminds me of the Collatz Conjecture . Here it is https://leetcode.com/problems/integer-replacement/ 397. Integer Replacement Medium 375 326 Add to List Share 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: Input: 8 Output: 3 Explanation: 8 -> 4 -> 2 -> 1 Example 2: Input: 7 Output: 4 Explanation: 7 -> 8 -> 4 -> 2 -> 1 or 7 -> 6 -> 3 -> 2 -> 1 The idea is to implement the rules mentioned in the problem statement, but with the following observations and optimizations: 1) Use a static hash table to keep track of the results. That's your cache 2) Use long instead of int to avoid overflows 3) Last but not least, optimize for when N is a power of 2. If N is a power of 2, the solution if Log(N,2). To ch