Constraints

• 0 <= n <= 10^18

Examples

Solution

def solution(n):
    from functools import lru_cache
    n = abs(n)

    @lru_cache(None)
    def dp(x):
        if x == 0:
            return 0
        if x == 1:
            return 1
        if x % 2 == 0:
            return dp(x // 2)
        return 1 + min(dp((x - 1) // 2), dp((x + 1) // 2))

    return dp(n)

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

Hints

1. If n is even, think about factoring out a power of 2.
2. If n is odd, your first move must make it even: compare n - 1 and n + 1.

Constraints

• 0 <= len(arr) <= 2 * 10^5
• 1 <= k <= 2 * 10^5

Examples

Solution

def solution(arr, k):
    if k <= 0:
        return 0
    n = len(arr)
    freq = {}
    distinct = 0
    left = 0
    best = n + 1

    for right, value in enumerate(arr):
        if freq.get(value, 0) == 0:
            distinct += 1
        freq[value] = freq.get(value, 0) + 1

        while distinct >= k:
            best = min(best, right - left + 1)
            out = arr[left]
            freq[out] -= 1
            if freq[out] == 0:
                del freq[out]
                distinct -= 1
            left += 1

    return -1 if best == n + 1 else best

Time complexity: O(n). Space complexity: O(min(n, number of distinct values)).

Hints

1. A sliding window can track how many distinct values are inside the current range.
2. Once a window has at least k distinct numbers, try shrinking it from the left.

Constraints

• 0 <= len(prices) <= 2 * 10^5
• 1 <= prices[i] <= 10^9

Examples

Solution

def solution(prices):
    n = len(prices)
    final_sum = sum(prices)
    stack = []
    discounted = [False] * n

    for i, price in enumerate(prices):
        while stack and prices[stack[-1]] >= price:
            idx = stack.pop()
            final_sum -= price
            discounted[idx] = True
        stack.append(i)

    full_price_indices = [i for i, used_discount in enumerate(discounted) if not used_discount]
    return final_sum, full_price_indices

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

Hints

1. The phrase first smaller-or-equal value to the right suggests a monotonic stack.
2. When a new price resolves discounts for earlier items, update the total immediately.

Constraints

• 0 <= len(arr) <= 5000
• -10^9 <= arr[i] <= 10^9

Examples

Solution

def solution(arr):
    n = len(arr)
    if n == 0:
        return -1
    if n == 1:
        return arr[0]

    limit = n - 1
    sieve = [True] * (limit + 1)
    if limit >= 0:
        sieve[0] = False
    if limit >= 1:
        sieve[1] = False
    i = 2
    while i * i <= limit:
        if sieve[i]:
            for j in range(i * i, limit + 1, i):
                sieve[j] = False
        i += 1

    special_primes = [p for p in range(3, limit + 1) if sieve[p] and p % 10 == 3]

    dp = [0] * n
    dp[0] = arr[0]
    for i in range(1, n):
        best_prev = dp[i - 1]
        for p in special_primes:
            if p > i:
                break
            if dp[i - p] > best_prev:
                best_prev = dp[i - p]
        dp[i] = best_prev + arr[i]

    return dp[-1]

Time complexity: O(n * p), where p is the number of allowed prime jump lengths less than n. Space complexity: O(n + p).

Hints

1. Precompute all allowed jump lengths less than n with a sieve.
2. Let dp[i] be the best score for reaching index i.

Constraints

• 1 <= treeNodes <= 2 * 10^5
• 1 <= len(queries) <= 2 * 10^5
• nodes[i] is a lowercase English letter

Examples

Solution

def solution(treeNodes, nodes, nodeFrom, nodeTo, queries):
    n = treeNodes
    if n == 0:
        return [0] * len(queries)

    children = [[] for _ in range(n)]
    for a, b in zip(nodeFrom, nodeTo):
        children[a].append(b)

    bits = [1 << (ord(ch) - 97) for ch in nodes]
    answers = [0] * n

    from collections import defaultdict
    freq = defaultdict(int)
    freq[0] = 1

    stack = [(0, 0, 0)]
    while stack:
        u, mask, state = stack.pop()
        if state == 0:
            current = mask ^ bits[u]
            total = freq.get(current, 0)
            for b in range(26):
                total += freq.get(current ^ (1 << b), 0)
            answers[u] = total

            freq[current] += 1
            stack.append((u, current, 1))
            for v in reversed(children[u]):
                stack.append((v, current, 0))
        else:
            freq[mask] -= 1
            if freq[mask] == 0:
                del freq[mask]

    return [answers[u] for u in queries]

Time complexity: O(26 * n + q). Space complexity: O(n).

Hints

1. A multiset can be rearranged into a palindrome iff at most one character has odd frequency.
2. Track parity with a 26-bit mask and count ancestor-prefix masks along the current DFS path.

Constraints

• 1 <= len(throughput) <= 2 * 10^5
• 1 <= throughput[i], scale_cost[i], budget <= 10^18

Examples

Solution

def solution(throughput, scale_cost, budget):
    if not throughput:
        return 0

    low = min(throughput)
    high = max(throughput) + budget // min(scale_cost) + 1

    def can(target):
        total = 0
        for t, c in zip(throughput, scale_cost):
            if t < target:
                total += (target - t) * c
                if total > budget:
                    return False
        return True

    while low + 1 < high:
        mid = (low + high) // 2
        if can(mid):
            low = mid
        else:
            high = mid

    return low

Time complexity: O(n log M), where M is the answer range. Space complexity: O(1).

Hints

1. If you can achieve throughput T, then every smaller target is also achievable.
2. Binary search the answer and write a function that computes the cost of reaching a target minimum.

Constraints

• 0 <= N <= 4000
• 1 <= e1, t1, e2, c <= 10^9

Examples

Solution

def solution(N, e1, t1, e2, c):
    if N == 0:
        return 0

    best = float('inf')

    for x in range(N + 1):
        stairs = N - x
        energy = x * e1

        if energy < stairs * e2:
            continue

        total_time = x * t1
        feasible = True

        for _ in range(stairs):
            if energy <= 0:
                feasible = False
                break
            total_time += (c + energy - 1) // energy
            energy -= e2
            if energy < 0:
                feasible = False
                break

        if feasible and total_time < best:
            best = total_time

    return -1 if best == float('inf') else best

Time complexity: O(N^2). Space complexity: O(1).

Hints

1. Try every possible elevator stop x from 0 to N.
2. A choice is feasible only if the starting elevator energy is enough to pay for all remaining stair floors.

Constraints

• 1 <= len(reward1) == len(reward2) <= 2000
• 0 <= k <= n
• 0 <= reward1[i], reward2[i] <= 10^9

Examples

Solution

def solution(reward1, reward2, k):
    base = sum(reward2)
    deltas = sorted((a - b for a, b in zip(reward1, reward2)), reverse=True)
    return base + sum(deltas[:k])

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

Hints

1. Start by assigning every task to person B.
2. Switching task i from B to A changes the total by reward1[i] - reward2[i].

Constraints

• 0 <= len(layers) == len(energyReq) <= 2 * 10^5
• 0 <= layers[i], energyReq[i], K <= 10^18

Examples

Solution

def solution(layers, energyReq, K):
    n = len(layers)
    if n == 0:
        return []

    pref = [0] * (n + 1)
    for i, x in enumerate(layers):
        pref[i + 1] = pref[i] + x

    need = [pref[i + 1] + max(0, energyReq[i]) - K for i in range(n)]

    size = 1
    while size < n:
        size *= 2

    seg = [float('-inf')] * (2 * size)
    for i, v in enumerate(need):
        seg[size + i] = v
    for i in range(size - 1, 0, -1):
        seg[i] = max(seg[2 * i], seg[2 * i + 1])

    def first_greater(node, nl, nr, left, threshold):
        if nr <= left or seg[node] <= threshold:
            return n
        if nr - nl == 1:
            return nl
        mid = (nl + nr) // 2
        res = first_greater(node * 2, nl, mid, left, threshold)
        if res != n:
            return res
        return first_greater(node * 2 + 1, mid, nr, left, threshold)

    ans = [0] * n
    for i in range(n):
        j = first_greater(1, 0, size, i, pref[i])
        ans[i] = (n - i) if j == n else (j - i)

    return ans

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

Hints

1. Rewrite the pass condition using prefix sums.
2. For each i, you need the first j >= i where a precomputed threshold exceeds prefix[i].

Constraints

• 0 <= len(prices), len(queries) <= 2 * 10^5
• 1 <= prices[i], amount <= 10^18

Examples

Solution

def solution(prices, queries):
    from bisect import bisect_right

    pref = [0]
    for p in prices:
        pref.append(pref[-1] + p)

    ans = []
    for pos, amount in queries:
        start = pos - 1
        target = pref[start] + amount
        right = bisect_right(pref, target) - 1
        ans.append(right - start)

    return ans

Time complexity: O((n + q) log n). Space complexity: O(n).

Hints

1. Because prices are positive, prefix sums are strictly increasing.
2. For each query, use binary search on the prefix sum array.

Constraints

• 1 <= n <= 2 * 10^5
• len(edges) == n - 1

Examples

Solution

def solution(n, edges):
    if n == 0:
        return []

    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append((b, 1))
        adj[b].append((a, 0))

    res = [0] * n
    parent = [-1] * n
    order = []
    stack = [0]

    while stack:
        u = stack.pop()
        order.append(u)
        for v, w in adj[u]:
            if v == parent[u]:
                continue
            parent[v] = u
            res[0] += w
            stack.append(v)

    for u in order:
        for v, w in adj[u]:
            if v == parent[u]:
                continue
            res[v] = res[u] + (1 if w == 0 else -1)

    return res

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

Hints

1. First compute the answer for one root, such as 0.
2. When rerooting across an edge, the answer changes by exactly 1 in one direction or the other.

Constraints

• 0 <= len(perm) <= 2 * 10^5
• perm is a permutation of 1..n

Examples

Solution

def solution(perm):
    n = len(perm)
    if n == 0:
        return []

    pos = [0] * (n + 1)
    for i, value in enumerate(perm):
        pos[value] = i

    ans = []
    lo = n
    hi = -1
    for w in range(1, n + 1):
        p = pos[w]
        if p < lo:
            lo = p
        if p > hi:
            hi = p
        ans.append(1 if hi - lo + 1 == w else 0)

    return ans

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

Hints

1. Store the position of each value.
2. As w grows from 1 to n, update only the current minimum and maximum position.