10 lines + 0ms bit counting solution - O(1) time, O(1) space
Idea\nI was heavily inspired by @wisdompeak\'s O(log n) greedy recursive solution, and looked for more patterns and how to eliminate all the recursive calls and
**Idea**\nI was heavily inspired by @wisdompeak\'s [`O(log n)` greedy recursive solution](https://leetcode.com/problems/the-earliest-and-latest-rounds-where-players-compete/discuss/1271531/Greedy-log(N)-solution), and looked for more patterns and how to eliminate all the recursive calls and loops. \n\nThis problem turns out to have a pretty simple solution. A key insight also came from @alanlzl\'s post: we can assume that `first` is closer to the left than `second` is to the right.\n\n1. **Finding Latest**: The optimal strategy for getting the latest round is to push `first` and `second` into positions 1 and 2, so all players left of \'second\' should try to lose. This is always possible to do if `second` is left of or at the middle, after which we return the most significant bit of n (rounds left). If `second` is close to the right edge, we can\'t push it to position 2, and `first` will eliminate at least one player to the right of `second` each round.\n\n2. **Finding Earliest**: It\'s usually possible to win in around 2-3 rounds. This is intuitive by the huge amount of control we have for where `first` and `second` will go in the next round, especially if there are many spaces between `first` and `second`. However, the position of each player only moves left, so we may need to wait some rounds for the midpoint of our player list to fall between `first` and `second`, in which case all players left of `second` should try to win.\n\n**Complexity**\nAssuming that we can read the number of trailing zeroes and leading zeroes from `n` in `O(1)` time, e.g. with the builtin assembly functions, there are a fixed number of operations. There\'s no recursion or loops (and both versions can be done without any function calls), and our only memory usage is 2 or 3 ints. \n* Time complexity: `O(1)` if `n` fits in a machine word / 64 bits\n* Space complexity: `O(1)`\n\t\n\n**C++:**\n\n```c++\nclass Solution {\npublic:\n    vector<int> earliestAndLatest(int n, int first, int second) {\n        if (first + second == n + 1) return {1, 1};\n        if (first + second > n + 1) tie(first, second) = make_tuple(n+1-second, n+1-first);\n        \n        int ans_earliest = 1, ans_latest = min(32 - __builtin_clz(n-1), n+1-second);\n        if (first + second==n){\n            if (first % 2 == 0) ans_earliest = first+2 < second? 2: 1 + __builtin_ctz(first);\n        }\n        else if (first+1 == second){\n            ans_earliest = 32 - __builtin_clz((n-1) / (first+second-1));\n            ans_earliest += __builtin_ctz((n-1)>>ans_earliest);\n        }\n        else if (first+second <= (n+1)/2) ans_earliest = 32 - __builtin_clz((n-1) / (first+second-1));\n        return {ans_earliest+1, ans_latest};\n    }\n};\n```\n\nSome more insight:\n\n* One trick used repeatedly is that the number of players transforms as: `n -> (n+1) / 2` every round. This means that the number of rounds by the time `n` becomes 2 is `ceiling(log_2(n))`, at which point the game ends. `ceiling(log_2(n))` can be computed efficiently as `# of bits in an int (32) - leading zeros(n-1)`. \n* This line requires special attention:\n```python\n# We want to know the number of rounds left until first + second >= n+1. \n# By the game rules, this is the minimum value of \n# k >= 0 such that ceiling(n / 2^k) < first + second.\n# With some rearranging, this becomes \nrounds_left = ceiling_of_log2((n + first + second - 2) // (first + second - 1))\n```\n\n\nMost of the Python code is just the bitwise implementations of C++ builtins/ assembly operations, working for up to 32 bit ints, as well as many comments. If `2**31 < n < 2**64`, a single extra line is required for these functions. These are fairly common; I found these 3 functions in a textbook. If `n` is tiny and needs much fewer than `32` bits, it\'s faster to just loop over the bits.\n\nI wrote out a full proof for each of the cases, but the \'earliest\' case is quite long. The key idea is to treat the problem as having 3 boxes, left, middle, and right, and trying to allocate an equal number of players into the left and right boxes. We get a choice of distributing `first-1` players to either the left or right boxes.  If `second` is at or right of the midpoint, we also get `n-first-second` players to place in the middle or right boxes, and so we can make the left and right boxes equal in 2 or 3 rounds, at which point we\'ve won if `first+1 != second`. If `second` is left of the midpoint, we only get `second-first-1` players to place in the middle or right boxes, which means the right box will end up larger than the left box. So we use induction to show that the optimal placement is having all `first-1` players left of `first` win their games, and all players between `first` and `second` try to win their games, minimizing the difference between right and left.\n\n**Python:**\n```python\nclass Solution:\n\tdef earliestAndLatest(self, n: int, first: int, second: int) -> List[int]:\n\t\tdef ceiling_of_log2(x: int) -> int:\n\t\t\t""" Return the ceiling of the integer log 2, i.e. index(MSB) - 1 + (1 if x not pow2) """\n\t\t\tassert 0 < x < 0x100000000\n\t\t\t# Use power of 2 test. offset is 1 iff x is NOT a power of 2\n\t\t\toffset = 1 if (x & (x - 1)) != 0 else 0\n\t\t\tx |= (x >> 1)\n\t\t\tx |= (x >> 2)\n\t\t\tx |= (x >> 4)\n\t\t\tx |= (x >> 8)\n\t\t\tx |= (x >> 16)\n\t\t\t# Remove offset to get floor_of_log2. floor(log2(x)) + 1 == ceil(log2(x)) iff x not a power of 2.\n\t\t\treturn popcount(x) - 1 + offset\n\n\t\tdef popcount(x: int) -> int:\n\t\t\t""" Return the number of set bits in 32 bit unsigned x (Hamming weight) """\n\t\t\tassert 0 <= x < 0x100000000\n\t\t\tx = x - ((x >> 1) & 0x55555555)\n\t\t\tx = (x & 0x33333333) + ((x >> 2) & 0x33333333)\n\t\t\treturn (((x + (x >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24\n\n\t\tdef count_trailing_zeroes(x: int) -> int:\n\t\t\t""" Return the number of trailing zeroes in 32 bit unsigned x > 0 (LSB + 1). This method is similar to\n\t\t\t\tbranchless binary search, but there are many other methods using the integer log2"""\n\t\t\tassert 0 < x < 0x100000000\n\t\t\tif x & 0x1: return 0  # odd x, quick break\n\t\t\tc = 1\n\t\t\tif (x & 0xffff) == 0:\n\t\t\t\tx >>= 16\n\t\t\t\tc += 16\n\t\t\tif (x & 0xff) == 0:\n\t\t\t\tx >>= 8\n\t\t\t\tc += 8\n\t\t\tif (x & 0xf) == 0:\n\t\t\t\tx >>= 4\n\t\t\t\tc += 4\n\t\t\tif (x & 0x3) == 0:\n\t\t\t\tx >>= 2\n\t\t\t\tc += 2\n\t\t\treturn c - (x & 0x1)\n\n\t\t# Base case, we can return instantly\n\t\tif first + second == n + 1: return [1, 1]\n\n\t\t# This ensures that \'first\' is closer to the left than \'second\' is to the right.\n\t\t# Also, crucially ensures that the sum of first and second is minimal among equivalent configs.\n\t\tif first + second >= n + 1: first, second = n + 1 - second, n + 1 - first\n\n\t\tfirst_plus_second = first + second\n\n\t\t# Special case if first + 1 == second, since we then need to find which round will have an even # of players\n\t\tif first + 1 != second and first_plus_second >= (n + 1) // 2 + 1:\n\t\t\tif first_plus_second == n:\n\t\t\t\t# If n is 4k + 2, first is 2k, and second is 2k+2, then parity of n also matters.\n\t\t\t\tif n % 4 == 2 and first + 2 == second:\n\t\t\t\t\t# Using n // 4 instead of n//4 + 1 because trailing_zeroes(x-1) = rounds until x is even\n\t\t\t\t\tans_earliest = 3 + count_trailing_zeroes(n // 4)\n\t\t\t\telse:\n\t\t\t\t\tans_earliest = 3 - (first % 2)\n\t\t\telse:\n\t\t\t\tans_earliest = 2\n\n\t\t# If we are in a special case: Players are too far left and close together to meet next round\n\t\telse:\n\t\t\tans_earliest = 1 + ceiling_of_log2((n + first_plus_second - 2) // (first_plus_second - 1))\n\t\t\tif first + 1 == second:\n\t\t\t\tans_earliest += count_trailing_zeroes(((n + (1 << (ans_earliest-1)) - 1) >> (ans_earliest-1)) - 1)\n\n\t\t# ceiling_of_log2 of n is the number of rounds left until there are exactly 2 players remaining, starting at n.\n\t\t# This implicitly assumes that optimal strategy for ans_latest is moving \'first\' and \'second\' to pos. 1 and 2\n\t\tans_latest = min(ceiling_of_log2(n), n + 1 - second)\n\n\t\treturn [ans_earliest, ans_latest]\n```
['C', 'Python']