C++ 29ms with Complexity of Log4(N) and Explanation


  • 9
    S

    First of all, if n is an odd number, then f(1..n) = f(1..n-1), because after the first round elimination, the last odd number will be removed.

    So let's consider even number.
    If the number of remaining numbers is even after the first round, which means the number is divided by 4. ex: 12. after first elimination, we have 2,4,6,8,10,12. then after the second round, we have 2, 6, 10. ,start from the beginning again => f(1..12) = f(2,6,10) = 2* f(1,3,5) = 2* [f(2,4,6) - 1] = 2 * [2f(1,2,3) - 1] = 4f(1..3) - 2; similarly we get f(n) = 4f(n/4) - 2. if n is divided by 4.

    If it is odd after first round, which means the number can't divided by 4, then during the second round, odd positioned numbers will be eliminated either process from beginning or from the end. ex: 10. first=> 2,4,6,8,10, second => 4, 8 => f(10) = 4*f(1..2)
    => f(n) = 4f(n/4)

    class Solution {
    public:
        int lastRemaining(int n) {
            if (n == 1) return 1;
            if (n <= 4) return 2;
            if (n % 2 != 0) n -= 1;
            if (n % 4 != 0) return 4 * lastRemaining(n/4);
            return 4 * lastRemaining(n/4) - 2;
        }
    };
    

  • 0
    B

    @singku said in C++ 29ms with Complexity of Log4(N) and Explanation:

    f(1..12) = f(2,6,10) = 2* f(1,3,5) = 2* [f(2,4,6) - 1] = 2 * [2f(1,2,3) - 1] = 4f(1..3) - 2

    how did that -1 come by ?


  • 0

    @bicepjai
    You should think about the meaning of f(1, 3, 5), and it means that you are trying to find the remained number of the sequence [1, 3, 5]. There are 3 possible results:

    1. f(1, 3, 5) = 1 which is the first number
    2. f(1, 3, 5) = 3 which is the second number
    3. f(1, 3, 5) = 5 which is the third number

    No matter what the result is, the result of f(2, 4, 6) should be the same index as f(1, 3, 4):

    1. If the result is the first number, so f(2, 4, 6) = 2
    2. If the result is the second number, so f(2, 4, 6) = 4
    3. If the result is the third number, so f(2, 4, 6) = 6

    So you can see that f(2, 4, 6) = f(1, 3, 5) + 1 just because that every number of former is bigger by 1 than that of the latter.


Log in to reply
 

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