c++. slow 2 lines recursive solution and fast memorization solution


  • 1

    2 lines recursive :

    class Solution {
    public:
        int integerReplacement(long long n) {
            if (n == 1) return 0;
            return 1 + (n % 2 ? min(integerReplacement(n + 1), integerReplacement(n - 1)) : integerReplacement(n / 2));
        }
    };
    

    Memorization :

    class Solution {
    unordered_map<int, int> memo;
    public:
        int integerReplacement(long long n) {
            if (memo.count(n)) return memo[n];
            if (n == 1) return 0;
            if (n % 2 == 0) {
                memo[n] = 1 + integerReplacement(n / 2);
            }
            else {
                int upper = integerReplacement(n + 1);
                int lower = integerReplacement(n - 1);
                memo[n + 1] = upper;
                memo[n - 1] = lower;
                memo[n] = min(memo[n + 1], memo[n - 1]) + 1;
            }
            return memo[n];
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.