Java log(n) DP solution


  • 0
    G

    DP should not the fastest one but easy to understand.
    Formular:
    dp[n] = dp[n/2] + 1, when n is an even number;
    dp[n] = min(dp[(n-1)/2]+2, dp[(n+1)/2]+2), when n is an odd number.
    With cache only O(log2(n)).

    // Cache
      Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    
      public int integerReplacement(int n) {
        if (n < 2)  return 0;
        if (n == 2)  return 1;
        Integer cache = map.get(n);
        if (cache != null) {
          return cache;
        }
        int min = n % 2 == 0 ? integerReplacement(n >> 1) + 1
            : (n + 1) > 0 ? Math.min(integerReplacement((n - 1) >> 1) + 2, integerReplacement((n + 1) >> 1) + 2) : Math.min(integerReplacement((n - 1) >> 1) + 2, integerReplacement(n >> 1 + 1) + 2);
        map.put(n, min);
        return min;
      }
    

Log in to reply
 

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