Leetcode #397. Integer Replacement

[yokostan]

'Brute Force' recursion:

class Solution {
    public int integerReplacement(int n) {
        if (n == 1) return 0;
        if (n == Integer.MAX_VALUE) return integerReplacement(n - 1);
        if (n % 2 == 0) {
            return integerReplacement(n/2) + 1;
        }
        if (n % 2 == 1) {
            return 1 + Math.min(integerReplacement(n - 1), integerReplacement(n + 1));
        }
        return 1;
    }
}

[yokostan]

bit manipulation runtime bears 100%:

class Solution {
    public int integerReplacement(int n) {
        int res = 0;
        while (n != 1) {
            if (n % 2 == 0) {
                n >>>= 1;
            }
            else if (n == 3 || (n + 1) % 4 != 0) {
                n--;
            }
            else n++;
            res++;
        }
        return res;
    }
}

https://leetcode.com/problems/integer-replacement/discuss/87920/A-couple-of-Java-solutions-with-explanations