modeling by arithmetic progression


  • 0
    Y

    The list is a arithmetic progression.
    It can be represent by a vector v = (S, N, D). S means the value of first element, N means number of element in this list, D means difference between the consecutive elements.
    So the original list is (S=1,N=n,D=1).
    After each elimination, the list will remain a arithmetic progression. N will be N/2; D will be 2*D; S will be S or S+D;
    class Solution {
    public:
    int lastRemaining(int n) {
    int D(1);
    int S(1);
    bool forward(true);
    while (n > 1) {
    if (forward) {
    S += D;
    } else {
    if (n&1) {
    S += D;
    }
    }
    n >>= 1;
    forward = !forward;
    D <<= 1;
    }
    return S;
    }
    };


Log in to reply
 

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