O(logN) solution. clear break down


  • 18
    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.


  • 3
    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!

Log in to reply
 

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