Share my 6ms C code


  • 2
    Z

    Only use int type, no special treatment for INT_MAX

    int myRP(int n, int k) {
        if (n == 1) return k;
        if (n % 2) {
            int result1 = myRP(((n - 1)>>1) + 1, k + 2);
            int result2 = myRP(n - 1, k + 1);
            return result1 < result2 ? result1 : result2;
        } else {
            return myRP(n>>1, k + 1);
        }
    }
    
    int integerReplacement(int n) {
        return myRP(n, 0);
    }
    

  • 0
    S

    Clever answer to handle (n+1)/2 case when n = INT_MAX.

    class Solution {
    public:
        int integerReplacement(int n) {
            return notebook(n, 0);
        }
    private:
        int notebook(int n, int k) {
            if (n == 1) return k;
            if (n % 2) {
                // case 1: plus 1 and then divided by 2 => (n+1)/2
                int p1 = notebook(((n-1) >> 1) + 1, k + 2);
                // case 2: minus 1 and then divided by 2 => (n-1)/2
                int p2 = notebook((n-1) >> 1, k + 2);
                return std::min(p1, p2);
            } else {
                return notebook(n >> 1, k + 1);
            }
        }
    };
    

Log in to reply
 

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