Most Self-Explain C++ Solution


  • 0
    J
    class Solution {
      public:
        int lastRemaining(int n) { return reduce(1, n, 1, FORWARD); }
    
      private:
        enum TURN { FORWARD, BACKWARD };
        int reduce(int from, int to_hasEnd, int num_gap, TURN turn) {
            int amount = (to_hasEnd - from) / num_gap + 1;
            if (amount == 1) {
                return from;
            }
    
            switch (turn) {
            case FORWARD:
                if (amount % 2 == 1) {
                    return reduce(from, to_hasEnd - num_gap, num_gap, FORWARD);
                } else {
                    return reduce(from + num_gap, to_hasEnd, num_gap * 2, BACKWARD);
                }
    
            case BACKWARD:
                if (amount % 2 == 1) {
                    return reduce(from + num_gap, to_hasEnd, num_gap, BACKWARD);
                } else {
                    return reduce(from, to_hasEnd - num_gap, num_gap * 2, FORWARD);
                }
            }
        }
    };
    

Log in to reply
 

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