Javascript easy recursion o(logn) solution


  • 0
    S

    We can easily find that the end of the recursion is n === 1.
    The key point is to find the start number of every number sequence.

    There are only two type of case.
    One case as below.

    1,2,3,4,5,6
    2,4,6
    4
    

    Anthor case.

    1,2,3,4,5,6,7,8,9
    2,4,6,8
    2,6
    6
    

    when the order is positive-going, next start is start + Math.pow(2, pow),pow is accumulate by one everytime.

    when the order is reverse, and num is an even, this is the same case as positive-going.

    when the order is reverse, but num is an odd, don't accumulate.

    sorry for bad English =_=;

    var lastRemaining = function(n, isReverse, start, pow) {
        start = start || 1;
        pow = pow || 0;
        if(n === 1) {
            return start;
        }
        
        var isOdd;
        if(!isReverse) {
            isOdd = false;
        } else {
            isOdd = !(n % 2);
        }
        
        start = isOdd ? start : start + Math.pow(2, pow);
        return lastRemaining(n >> 1, !isReverse, start, pow + 1)
    };
    

Log in to reply
 

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