Constraints

• 0 <= len(A) <= 200000
• Each element of A is an integer and may be negative or larger than n-1
• Your algorithm should use O(1) extra space
• Your algorithm should run in O(n) time

Examples

Solution

def solution(A):
    n = len(A)
    i = 0

    while i < n:
        x = A[i]

        if x < 0 or x >= n:
            return False

        if x == i:
            i += 1
            continue

        if A[x] == x:
            return False

        A[i], A[x] = A[x], A[i]

    return True

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

Hints

1. Try placing each value x at index x by swapping until the current index is correct.
2. If a value is out of range, or if its target index already holds the same value, you can reject immediately.

Constraints

• -1000000.0 <= base <= 1000000.0
• -2147483648 <= exp <= 2147483647
• Do not use library exponentiation
• Target time complexity: O(log |exp|)
• Target extra space: O(1)

Examples

Solution

def solution(base, exp):
    if exp == 0:
        return 1.0

    if base == 0.0:
        if exp < 0:
            raise ZeroDivisionError('0.0 cannot be raised to a negative power')
        return 0.0

    result = 1.0
    b = float(base)
    e = exp

    if e < 0:
        b = 1.0 / b
        e = -e

    while e > 0:
        if e & 1:
            result *= b
        b *= b
        e >>= 1

    return result

Time complexity: O(log |exp|). Space complexity: O(1).

Hints

1. Write the exponent in binary: each bit tells you whether to multiply the current power into the answer.
2. For a negative exponent, invert the base first and then work with the absolute value of the exponent.