O(logn) 4ms solution


  • 1
    V

    My idea was to reduce the odd n to the number (n+1 or n-1) that has more factors of 2. Since more factors of 2 will always give us the shortest way to get to 1.

    Handling MAX_VALUE case by taking abs().

    n gets reduced by half in each step. Hence, O(logn).

    Code:

    public int integerReplacement(int n) {
        int steps = 0;
        while (n > 1)
        {
            if (n%2 == 0)
            {
                steps++;
                n >>= 1;
            }
            else
            {
                int temp1 = n-1;
                int temp2 = n+1;
                
                int tempSteps = 1;
                // Reduce n to the number that has more factors of 2
                while (temp1 % 2 == 0 && temp2 % 2 == 0)
                {
                    temp1 >>= 1;
                    temp2 >>= 1;
                    tempSteps++;
                }
                
                // To handle MAX_VALUE+1 case
                temp2 = Math.abs(temp2);
              
                if (temp1 == 1)
                {
                    n = temp1;
                }
                else if (temp2 == 1)
                {
                    n = temp2;
                }
                else if (temp1 % 2 > 0)
                {
                    n = temp2;
                }
                else
                {
                    n = temp1;
                }
                
                steps += tempSteps;
            }
        }
        
        return steps;
    }

  • 0
    G

    Good solution without recursion


Log in to reply
 

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