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

• 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;
}
};
``````

• 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 ?

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

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