Constraints

• 0 <= x <= 10^12
• Do not use math.sqrt, pow, or **
• Absolute error before rounding should be at most about 1e-6

Examples

Solution

def solution(x):
    if x == 0:
        return 0.0

    low, high = 0.0, max(1.0, float(x))
    eps = 1e-7

    while high - low > eps:
        mid = (low + high) / 2.0
        if mid * mid > x:
            high = mid
        else:
            low = mid

    return round((low + high) / 2.0, 6)

Time complexity: O(log(max(1, x) / 1e-7)). Space complexity: O(1).

Hints

1. The function f(y) = y * y is monotonic for y >= 0, so binary search works well.
2. A safe search interval is [0, max(1, x)] so that both very small and very large inputs are covered.

Constraints

• 0 <= len(arr) <= 2 * 10^5
• -10^9 <= arr[i] <= 10^9
• Use O(1) extra space beyond a few variables
• Strict inequality is required: every even-position value must be smaller than every odd-position value

Examples

Solution

def solution(arr):
    n = len(arr)
    if n <= 1:
        return arr

    def sift_down(start, end):
        root = start
        while True:
            child = 2 * root + 1
            if child > end:
                break
            if child + 1 <= end and arr[child] < arr[child + 1]:
                child += 1
            if arr[root] < arr[child]:
                arr[root], arr[child] = arr[child], arr[root]
                root = child
            else:
                break

    for start in range((n - 2) // 2, -1, -1):
        sift_down(start, n - 1)

    for end in range(n - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]
        sift_down(0, end - 1)

    lower_size = n // 2
    if lower_size > 0 and arr[lower_size - 1] >= arr[lower_size]:
        return []

    min_val = arr[0]
    shift = -min_val
    for i in range(n):
        arr[i] += shift

    base = arr[-1] + 1

    for target in range(n):
        if target % 2 == 0:
            src = n - 1 - target // 2
        else:
            src = (target - 1) // 2
        new_val = arr[src] % base
        arr[target] += new_val * base

    for i in range(n):
        arr[i] = arr[i] // base - shift

    return arr

Time complexity: O(n log n). Space complexity: O(1).

Hints

1. After sorting, all values that go to even positions must come from the lower half, and all values that go to odd positions must come from the upper half.
2. If you want O(1) extra space after sorting, think about encoding both the old and new value inside the same array cell.