O(logN) solution. clear break down


  • 20
    B
        public int lastRemaining(int n) {
          return leftToRight(n);
        }
    
        private static int leftToRight(int n) {
          if(n <= 2) return n;
          return 2 * rightToLeft(n / 2);
        }
    
        private static int rightToLeft(int n) {
          if(n <= 2) return 1;
          if(n % 2 == 1) return 2 * leftToRight(n / 2);
          return 2 * leftToRight(n / 2) - 1;
        }
    

  • 0
    A

    @beijunyi Easy to understand, thanks for sharing.


  • 5
    Z

    Clever use of mutual recursion, almost self-explained! I reduce the base case a little bit and add some comments for easier understand.

        public int lastRemaining(int n) {
            return leftToRight(n);
        }  
        
        // eliminate [1...n] first from left to right, then alternate
        private int leftToRight(int n) {
            if (n == 1) return 1;
            // scan from left to right is simple, the length of array doesn't matter
            // [1, 2, 3, 4] -> 2 * [1, 2]
            // [1, 2, 3, 4, 5] -> 2 * [1, 2]
            return 2 * rightToLeft(n / 2);
        }
        
        // eliminate [1...n] first from right to left, then alternate
        private int rightToLeft(int n) {
            if (n == 1) return 1;
            // if the length of array is even, we will get only odd number
            // [1, 2, 3, 4] -> [1, 3] = 2 * [1, 2] - 1
            if (n % 2 == 0) return 2 * leftToRight(n / 2) - 1;
            // else if the length of array is odd, we will get only even number
            // [1, 2, 3, 4, 5] -> [2, 4] = 2 * [1, 2]
            else return 2 * leftToRight(n / 2);
        }
    

  • 0
    T
    This post is deleted!

  • 0

    It took me some time to fully understand this recursive approach, but I think this is a great solution! Here is a very detailed explanation if anyone is wondering:

    Denote L as traversing [1,...,n] from left to right, R as traversing [1,...,n] from right to left.

    • When n is odd:
      L(1234567) = R(246) = R(123)*2
      R(1234567) = L(246) = L(123)*2

    • When n is even:
      L(123456) = R(246) = R(123)*2
      R(123456) = L(135) = L(123) + 1 (a bit tricky)


Log in to reply
 

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