DFS with pruning


  • 0
    H
    public class Solution {
        
        private int min;
        
        public int integerReplacement(int n) {
            this.min = Integer.MAX_VALUE;
            integerReplacement(n, 0);
            return min;
        }
        
        private void integerReplacement(int n, int step) {
            if (step >= min)
                return;
            if (n == 1) {
                min = Math.min(min, step);
                return;
            }
            if ((n & 1) == 0) {
                // even
                integerReplacement(n >>> 1, step + 1);
            } else {
                // odd
                integerReplacement(n + 1, step + 1);
                integerReplacement(n - 1, step + 1);
            }
        }
    }
    
    

  • 0
    N

    Can you tell me how you dealt with integer overflow when n=Interger.Max_VALUE?


Log in to reply
 

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