Simple iterative C# solution O(logn) runtime with explanation


  • 0
    W

    The crux of my solution was in determining the choice trees and the priority to take each choice. Fortunately there is only one correct choice to be made at each fork, so we don't need to recurse/backtrack.

    I found this following example most useful - start at 9, moving left to right, forking when odd:

                           /-> 4 -> 2 -> 1
                          /
                 /-> 6 -> 3 -> 2 -> 1
                /
    9 --->10 -> 5 -> 4 -> 2 -> 1
      \
       \-> 8 -> 4 -> 2 -> 1
    
    

    From the example above, it becomes apparent that the following rules should apply:

    For odd values:

    1. Try to decrement only if the decremented result/2 is even (find the shorter subtree!)
    2. Increment if the incremented result/2 is even
    

    For even values:

    1. There's no choice, divide by two.
    

    Two edge cases that I needed to deal with were max signed int and when n==3.

    To deal with max signed int (odd value), I used the basic integer property that:

    (odd+1)/2 == odd/2 + 1
    

    My solution effectively divides the input in half every iteration, so I believe the runtime is O of log base 2 of n, which is O(logn). O(1) space used for constants.

    public int IntegerReplacement(int n) {
        var count = 0;
        while (n!=1) {
            var isOdd = (n%2==1);
            if(isOdd) {
                var downChoiceVal = (n-1)/2;
                // deal with edge case of n==3
                if(downChoiceVal%2==0 || downChoiceVal==1) {
                    n=(n-1)/2;
                    count++;
                }
                else {
                    // deal with edge case of int32.max
                    n=n/2+1;
                    count++;
                }
            }
            else n /= 2;
            count++;
        }
        return count;
    }
    

Log in to reply
 

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