Two Solutions


  • 0
    K
    1. Naive recursion solution, need to pay attention to overflow:
      public int integerReplacement(int n) {
      return op((long)n);
      }

      private int op(long n) {
      int result = 0;
      while (n > 1) {
      if (n % 2 == 1) {
      result++;
      return result + Math.min(op(n+1), op(n-1));
      } else {
      n >>= 1;
      }
      result++;
      }
      return result;
      }

    2. A better solution, but a little tricky. In general reducing the number of bits as much as possible in one operation is good since shifting to the right is much faster than +1 or -1. If we analyze +1 and -1 further, we can find out that:

    • for consecutive 1s like 111, plus 1 can reduce more 1s
    • for patterns end with 01, minus one can reduce one bit while plus one won't affect the number of bits
    • Somehow this strategy doesn't seem right for n = 3 since plus one reduce 1 bit but introduce 2 shifts.
    • n = Integer.MAX_VALUE will introduce overflow, we can return 32 in this case.
      Solution:
      public int integerReplacement(int n) {
      int result = 0;
      if (n == Integer.MAX_VALUE) {
      return 32;
      }
      while (n > 1) {
      if ((n & 1) == 1) {
      if (n != 3 && (n & 2) == 2) {
      n++;
      } else {
      n--;
      }
      } else {
      n >>= 1;
      }
      result++;
      }
      return result;
      }

Log in to reply
 

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