1
class Solution:
2
    def earliestAndLatest(self, n: int, first: int, second: int) -> List[int]:
3
        def ceiling_of_log2(x: int) -> int:
4
            """Return the ceiling of the integer log 2, i.e. index(MSB) - 1 + (1 if x not pow2)"""
5
            assert 0 < x < 0x100000000
6
            # Use power of 2 test. offset is 1 iff x is NOT a power of 2
7
            offset = 1 if (x & (x - 1)) != 0 else 0
8
            x |= x >> 1
9
            x |= x >> 2
10
            x |= x >> 4
11
            x |= x >> 8
12
            x |= x >> 16
13
            # Remove offset to get floor_of_log2. floor(log2(x)) + 1 == ceil(log2(x)) iff x not a power of 2.
14
            return popcount(x) - 1 + offset
15

16
        def popcount(x: int) -> int:
17
            """Return the number of set bits in 32 bit unsigned x (Hamming weight)"""
18
            assert 0 <= x < 0x100000000
19
            x = x - ((x >> 1) & 0x55555555)
20
            x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
21
            return (((x + (x >> 4) & 0xF0F0F0F) * 0x1010101) & 0xFFFFFFFF) >> 24
22

23
        def count_trailing_zeroes(x: int) -> int:
24
            """Return the number of trailing zeroes in 32 bit unsigned x > 0 (LSB + 1). This method is similar to
25
            branchless binary search, but there are many other methods using the integer log2
26
            """
27
            assert 0 < x < 0x100000000
28
            if x & 0x1:
29
                return 0  # odd x, quick break
30
            c = 1
31
            if (x & 0xFFFF) == 0:
32
                x >>= 16
33
                c += 16
34
            if (x & 0xFF) == 0:
35
                x >>= 8
36
                c += 8
37
            if (x & 0xF) == 0:
38
                x >>= 4
39
                c += 4
40
            if (x & 0x3) == 0:
41
                x >>= 2
42
                c += 2
43
            return c - (x & 0x1)
44

45
        # Base case, we can return instantly
46
        if first + second == n + 1:
47
            return [1, 1]
48

49
        # This ensures that 'first' is closer to the left than 'second' is to the right.
50
        # Also, crucially ensures that the sum of first and second is minimal among equivalent configs.
51
        if first + second >= n + 1:
52
            first, second = n + 1 - second, n + 1 - first
53

54
        first_plus_second = first + second
55

56
        # Special case if first + 1 == second, since we then need to find which round will have an even # of players
57
        if first + 1 != second and first_plus_second >= (n + 1) // 2 + 1:
58
            if first_plus_second == n:
59
                # If n is 4k + 2, first is 2k, and second is 2k+2, then parity of n also matters.
60
                if n % 4 == 2 and first + 2 == second:
61
                    # Using n // 4 instead of n//4 + 1 because trailing_zeroes(x-1) = rounds until x is even
62
                    ans_earliest = 3 + count_trailing_zeroes(n // 4)
63
                else:
64
                    ans_earliest = 3 - (first % 2)
65
            else:
66
                ans_earliest = 2
67

68
        # If we are in a special case: Players are too far left and close together to meet next round
69
        else:
70
            ans_earliest = 1 + ceiling_of_log2(
71
                (n + first_plus_second - 2) // (first_plus_second - 1)
72
            )
73
            if first + 1 == second:
74
                ans_earliest += count_trailing_zeroes(
75
                    ((n + (1 << (ans_earliest - 1)) - 1) >> (ans_earliest - 1)) - 1
76
                )
77

78
        # ceiling_of_log2 of n is the number of rounds left until there are exactly 2 players remaining, starting at n.
79
        # This implicitly assumes that optimal strategy for ans_latest is moving 'first' and 'second' to pos. 1 and 2
80
        ans_latest = min(ceiling_of_log2(n), n + 1 - second)
81

82
        return [ans_earliest, ans_latest]