Solve these algorithmic problems

You are given the following independent coding tasks. For each task, design an algorithm and implement a function that returns the requested output.

---

1) Minimum operations to reduce n to 0

You are given a positive integer n.

Operation: choose an integer i >= 0 and replace n with n - 2^i or n + 2^i.

Assume you must keep n >= 0 after each operation.

Goal: return the minimum number of operations needed to make n = 0.

Input: n (fits in 64-bit signed integer)

Output: minimum operations (integer)

---

2) Shortest subarray with at least k distinct integers

Given an integer array arr and integer k, call a subarray good if it contains at least k distinct values.

Goal: return the length of the shortest good subarray; if no such subarray exists, return -1.

Example: arr = [1, 2, 2, 3, 1, 4], k = 3 → answer is 3 (e.g., subarray [2,3,1]).

---

3) First discount to the right (next <= price)

Given an array prices.

For each index i, find the first index j > i such that prices[j] <= prices[i].

• If such j exists, the final price is prices[i] - prices[j].
• Otherwise, the item is sold at full price prices[i].

Return two things:

1. The sum of all final prices.
2. The indices (0-based) of items sold at full price, in increasing order, as a space-separated string (or empty string if none).

---

4) Balanced prefixes in a permutation

You are given a permutation p of 1..n.

For a given k (1 <= k <= n), say k is balanced if there exists some subarray p[l..r] that is a permutation of 1..k (each of 1..k appears exactly once in the subarray).

Goal: for every k = 1..n, determine if k is balanced and return a binary string s of length n where s[k-1] = '1' if balanced else '0'.

---

5) Elevator + stairs: minimize time difference

There are n floors to reach from floor 0 to floor n.

You may take the elevator for exactly x floors first (where 0 <= x <= n), then walk the remaining n - x floors.

• Elevator: each elevator floor gives you e1 energy and takes t1 time.
• After the elevator, you start stairs with curr_energy = x * e1.
• Stairs: for each walked floor:
  • Time cost for that floor is ceil(c / curr_energy) (given constant c > 0).
  • Energy decreases by e2 after climbing that floor.
  • Energy must never become negative during the stair process.

Goal: choose x to minimize |T_elevator(x) - T_stairs(x)| and return that minimum absolute difference.

If for some x the stairs part is infeasible due to energy dropping below 0, that x cannot be chosen.

---

6) Maximum score to reach end with special jumps

Given an integer array arr of length n.

You start at index 0 with score arr[0], and must finish at index n-1.

From index i, you may jump to:

• i + 1, or
• i + d where d is in the set {3, 13, 23, 33, ...} and d is prime (i.e., prime numbers whose last digit is 3).

(Only jumps that stay within bounds are allowed.)

Goal: return the maximum achievable score at n-1, or -1 if n-1 is unreachable.

---

7) Choose a root to minimize edge reversals

You are given a directed graph on n nodes labeled 0..n-1 with n-1 edges such that the underlying undirected graph is a tree.

You may pick any node as the root. You want to reverse as few directed edges as possible so that after reversals, every edge points away from the root.

Goal: return a root node that achieves the minimum number of reversals (if multiple, returning any one is acceptable).

---

8) Purchase optimization queries (consecutive buying from a position)

Given an array prices (length n) and queries of the form (pos, amount):

• pos is 1-based.
• Starting at index pos-1, you can buy items consecutively to the right as long as the total cost does not exceed amount.

Goal: for each query, return the maximum number of items you can buy.

Return an array of answers in query order.

---

9) Longest subsequence with sum limit (multiple queries)

Given an array nums and an array queries.

For each query value q, you may pick a subsequence (not necessarily contiguous) of nums to maximize the subsequence length such that the sum of chosen elements is <= q.

Goal: return the maximum length for each query.

---

10) Maximize pipeline throughput under scaling budget

There are m services in a pipeline. Service i+1 consumes the output of service i.

• Initial throughput is throughput[i].
• You may scale service i any number of times; each unit increase of throughput costs scalecost[i].
• Total spend across all services must be <= budget.

Assume the end-to-end pipeline throughput equals min(throughput[i]) after scaling.

Goal: return the maximum achievable pipeline throughput.

---

11) Starting-from-each-level adventure scoring

You are given arrays layers and energy of length n, and an initial energy K.

If you start at level i with current energy K:

• To attempt level j (starting from j=i and increasing):
  1. You must pay layers[j] energy.
  2. After paying, if remaining energy >= energy[j], you pass the level and gain 1 point; otherwise you fail and the run stops immediately.

Goal: return an array score of length n where score[i] is the number of consecutive levels you can pass starting from level i.

---

12) Assign tasks to two people with exactly k tasks for person 1

There are n tasks. If task i is done by person 1, you gain reward1[i]. If done by person 2, you gain reward2[i].

Constraint: person 1 must do exactly k tasks (and person 2 does the rest).

Goal: maximize total reward and return that maximum.

---

13) Count palindromic downward paths ending at queried nodes in a tree

You are given a tree of treeNodes nodes labeled 0..treeNodes-1, rooted at node 0. Each node u has a lowercase letter label nodes[u].

A downward path that ends at node u and starts at some ancestor a on the root-to-u path (including possibly a = u) is considered palindromic-rearrangeable if the multiset of letters along the path can be permuted to form a palindrome (equivalently: at most one character appears an odd number of times).

You are given queries, a list of node indices.

Goal: for each queried node q, return the number of ancestors a on the path from root to q such that the path a -> ... -> q is palindromic-rearrangeable.

Input format: edges are provided by parallel arrays nodeFrom, nodeTo (undirected edges).

Output: array of answers aligned with queries.

Minimum Operations to Reduce n to 0

You are given a non-negative integer n.

Operation: choose an integer i >= 0 and replace n with n - 2^i or n + 2^i, keeping n >= 0 after each step.

Goal: return the minimum number of operations needed to make n = 0.

The answer equals the number of nonzero digits in the non-adjacent form (NAF) of n: scan bits from least significant; on a run of trailing 1s it is cheaper to add 1 (turning the run into a single higher carry) than to clear each bit, so each maximal block of 1s costs at most 2 operations.

Constraints

• 0 <= n < 2^63
• n fits in a 64-bit signed integer

Examples

Example 1

Input: (0,)
Output: 0

Explanation: Already zero, no operations needed.

Example 2

Input: (1,)
Output: 1

Explanation: Subtract 2^0.

Hints

1. Each operation adds or subtracts a single power of two, so the answer is the minimum number of signed powers of two that sum to n.
2. That minimum equals the number of nonzero digits in the non-adjacent form (NAF) of n.
3. Process bits from the bottom: a lone set bit costs 1; a run of consecutive set bits is cheaper to clear by adding 1 (creating one carry) than by subtracting each bit.

Shortest Subarray With At Least k Distinct Integers

Given an integer array arr and an integer k, a subarray is good if it contains at least k distinct values.

Goal: return the length of the shortest good subarray, or -1 if none exists.

Use a sliding window: expand the right edge to gain distinct values, and whenever the window already has >= k distinct values, shrink from the left to find the shortest window ending at the current right index.

Constraints

• 0 <= len(arr) <= 10^5
• 1 <= k
• values may repeat and may be negative

Examples

Example 1

Input: ([1,2,2,3,1,4], 3)
Output: 3

Explanation: [2,3,1] has 3 distinct values and length 3, the shortest possible.

Example 2

Input: ([1,1,1], 2)
Output: -1

Explanation: Only one distinct value exists, so no subarray has 2 distinct.

Hints

1. A two-pointer sliding window works because adding elements only increases the distinct count and removing elements only decreases it.
2. Keep a frequency map; the distinct count rises when a count goes 0 -> 1 and falls when it goes 1 -> 0.
3. While the window has at least k distinct values, record its length and shrink from the left to find the minimum window ending at the current right pointer.

First Discount to the Right

Given an array prices, for each index i find the first index j > i with prices[j] <= prices[i].

• If such j exists, the item's final price is prices[i] - prices[j].
• Otherwise it is sold at full price prices[i].

Return a list [total, full_indices] where total is the sum of all final prices and full_indices is a space-separated string of the 0-based indices of items sold at full price (empty string if none).

The "next element to the right that is <= the current" is a classic monotonic-stack problem solved in one right-to-left pass.

Constraints

• 0 <= len(prices) <= 10^5
• prices can be any integers

Examples

Example 1

Input: ([8,4,6,2,3],)
Output: [15, '3 4']

Explanation: Discounts: 8-4, 4-2, 6-2; index 3 (2) and index 4 (3) have no smaller-or-equal to the right. Sum = 4+2+4+2+3 = 15.

Example 2

Input: ([10,1,1,6],)
Output: [16, '2 3']

Explanation: 10-1, 1-1, then indices 2 and 3 are full price. Sum = 9+0+1+6 = 16.

Hints

1. For each i you need the nearest index to the right whose value is <= prices[i] - this is a next-smaller-or-equal element query.
2. Sweep from right to left maintaining a stack of candidate indices, popping any whose value is strictly greater than the current price.
3. After resolving nxt[], sum the discounts and collect indices where no qualifying j exists for the full-price list.

Balanced Prefixes in a Permutation

You are given a permutation p of 1..n. Value k is balanced if some subarray p[l..r] is exactly a permutation of 1..k.

Goal: return a binary string s of length n where s[k-1] = '1' if k is balanced, else '0'.

Key insight: since p is a permutation, the values 1..k occupy k distinct positions. They form a contiguous subarray iff the span from their minimum position to their maximum position has width exactly k.

Constraints

• 1 <= n <= 10^5
• p is a permutation of 1..n

Examples

Example 1

Input: ([1,2,3],)
Output: 111

Explanation: Every prefix 1..k already sits contiguously at the front.

Example 2

Input: ([2,3,1,5,4],)
Output: 10101

Explanation: k=1 balanced ([1] at index 2); k=2 spans indices 0..2 width 3 != 2; k=3 spans 0..2 width 3; k=4 width 5 != 4; k=5 whole array.

Hints

1. Record pos[v] = the index where value v sits.
2. For a fixed k, the values 1..k occupy exactly k positions; they form one contiguous block iff (max position - min position + 1) == k.
3. Sweep k from 1 to n, maintaining running min and max of the positions seen so far - this gives an O(n) one-pass solution.

Elevator and Stairs: Minimize Time Difference

You must reach floor n from floor 0. You ride the elevator for x floors (0 <= x <= n), then walk the remaining n - x floors.

• Elevator: each floor gives e1 energy and takes t1 time, so T_elevator(x) = x * t1 and you start stairs with curr_energy = x * e1.
• Stairs: for each walked floor, time cost is ceil(c / curr_energy), then energy drops by e2. Energy must never go negative.

Goal: choose x to minimize |T_elevator(x) - T_stairs(x)|; skip any x whose stair phase becomes infeasible. Return the minimum absolute difference (or -1 if no x is feasible).

Constraints

• 0 <= x <= n
• c > 0
• energy must stay >= 0 throughout the stair phase

Examples

Example 1

Input: (3, 2, 5, 1, 4)
Output: 1

Explanation: x=1: elevator time 5, stairs ceil(4/2)+ceil(4/1)=2+4=6, diff=1 (minimum over all x).

Example 2

Input: (2, 5, 1, 2, 10)
Output: 1

Explanation: Best x yields difference 1.

Hints

1. Try every elevator count x from 0 to n; each fully determines both the elevator time and the starting stair energy.
2. Simulate the stair phase floor by floor, adding ceil(c / curr_energy) and subtracting e2; if energy reaches 0 before a floor or drops below 0, that x is infeasible.
3. Track the minimum |T_elevator - T_stairs| across all feasible x; return -1 if none are feasible.

Maximum Score With Special Jumps

Given an integer array arr of length n, start at index 0 with score arr[0] and finish at index n-1. From index i you may jump to i+1, or to i+d where d belongs to {3, 13, 23, 33, ...} (numbers ending in 3) and d is prime. Jumps must stay in bounds.

Goal: return the maximum achievable score at n-1, or -1 if it is unreachable.

This is a maximum-weight path on a DAG (edges always go forward), so a left-to-right DP over indices works.

Constraints

• 1 <= n
• arr may contain negative values
• allowed jumps are 1 and primes ending in digit 3

Examples

Example 1

Input: ([1,2,3,4],)
Output: 10

Explanation: 1->2->3->4 collects all values; the jump of 3 (0->3) gives only 1+4=5.

Example 2

Input: ([5],)
Output: 5

Explanation: Already at the last index with score 5.

Hints

1. The only allowed jump lengths are 1 and primes whose last digit is 3 (3, 13, 23, 43, 53, ...); precompute those below n.
2. All jumps go strictly forward, so process indices left to right with dp[i] = best score reaching i.
3. Relax dp[i+s] = max(dp[i+s], dp[i] + arr[i+s]) for every allowed step s; the answer is dp[n-1] or -1 if it stayed unreachable.

Choose a Root to Minimize Edge Reversals

You are given a directed graph on n nodes (0..n-1) with n-1 edges whose underlying undirected graph is a tree. Edges are given as a list of [u, v] meaning a directed edge u -> v.

Pick any node as root; reverse as few directed edges as possible so every edge points away from the root.

Goal: return a root achieving the minimum number of reversals (any one if several tie).

Compute the cost for root 0 with one traversal, then re-root: moving the root across an edge flips that one edge's contribution, so each node's cost differs from its parent's by exactly +/-1.

Constraints

• 1 <= n
• edges form a tree on the underlying undirected graph
• edges are directed u -> v

Examples

Example 1

Input: (4, [[0,1],[1,2],[3,2]])
Output: 0

Explanation: Rooting at 0 needs only the edge 3->2 reversed (1 reversal); other roots need more.

Example 2

Input: (2, [[1,0]])
Output: 1

Explanation: Edge points 1->0, so rooting at 1 needs zero reversals.

Hints

1. Build an undirected adjacency list where traversing in the edge's true direction costs 0 and against it costs 1 (a reversal).
2. A BFS/DFS from node 0 summing those costs gives the reversal count when 0 is the root.
3. Re-root with a second traversal: crossing an edge from parent to child flips exactly that edge's contribution, so res[child] = res[parent] + (1 - 2*w). Return the argmin.

Consecutive Purchase Queries

Given prices of length n and queries [pos, amount] (pos is 1-based): starting at index pos-1, buy items consecutively to the right while the running total cost stays <= amount.

Goal: for each query, return the maximum number of items you can buy. Return the answers in query order.

With a prefix-sum array (prices are non-negative so prefix sums are non-decreasing), each query is a binary search for the furthest reach whose cumulative cost stays within budget.

Constraints

• 1 <= pos <= n
• amount >= 0
• prices are non-negative

Examples

Example 1

Input: ([2,3,1,4], [[1,5],[2,4],[3,100],[4,3]])
Output: [2, 2, 2, 0]

Explanation: From pos 1 budget 5 buys 2+3; from pos 2 budget 4 buys 3+1; from pos 3 budget 100 buys 1+4; from pos 4 budget 3 cannot afford the 4.

Example 2

Input: ([5], [[1,4],[1,5]])
Output: [0, 1]

Explanation: Budget 4 cannot afford price 5; budget 5 buys exactly one item.

Hints

1. Precompute prefix sums so the cost of items [start, end) is prefix[end] - prefix[start].
2. Because prices are non-negative, prefix sums are non-decreasing, enabling binary search.
3. For each query find the largest end with prefix[end] <= prefix[start] + amount; the count is end - start.

Longest Subsequence With Sum Limit

Given an array nums and an array queries, for each query value q pick a subsequence of nums (any subset) maximizing its length subject to the chosen elements summing to <= q.

Goal: return the maximum length for each query.

To maximize count under a sum cap you greedily take the smallest elements: sort nums, build prefix sums, and binary search each query for how many of the smallest values fit.

Constraints

• 0 <= len(nums)
• elements assumed non-negative for the greedy to be optimal
• queries can be any non-negative values

Examples

Example 1

Input: ([4,5,2,1], [3,10,21,1])
Output: [2, 3, 4, 1]

Explanation: Sorted [1,2,4,5], prefix [0,1,3,7,12]; q=3 fits {1,2}=2, q=10 fits {1,2,4}=3, q=21 fits all 4, q=1 fits {1}=1.

Example 2

Input: ([], [0,5])
Output: [0, 0]

Explanation: No elements to pick, every query yields 0.

Hints

1. To maximize the number of chosen elements under a sum budget, always prefer the smallest values.
2. Sort nums and take a prefix sum; prefix[k] is the smallest possible sum of any k elements.
3. For each query q, binary search the largest k with prefix[k] <= q.

Maximize Pipeline Throughput Under Budget

A pipeline has m services in series; service i+1 consumes service i's output. Service i starts at throughput[i], and each unit increase costs scalecost[i]. Total spend must be <= budget. End-to-end throughput is min(throughput[i]) after scaling.

Goal: return the maximum achievable pipeline throughput.

The objective min(throughput) is monotonic in the target level T: higher T costs more. Binary search the largest T whose total raising cost stays within budget.

Constraints

• 1 <= m
• scalecost[i] >= 1
• budget >= 0

Examples

Example 1

Input: ([2,4,3], [1,2,1], 5)
Output: 4

Explanation: Raising all to 4 costs (4-2)*1 + 0 + (4-3)*1 = 3 <= 5; reaching 5 would cost 7.

Example 2

Input: ([5], [1], 100)
Output: 105

Explanation: One service, every budget unit buys one throughput unit: 5 + 100.

Hints

1. The achievable throughput is some target level T that every service is raised to (services already above T are left alone).
2. Cost to reach level T is sum over services with throughput[i] < T of (T - throughput[i]) * scalecost[i]; this is monotonically increasing in T.
3. Binary search the largest T whose cost is within budget; start the search at the current minimum throughput.

Starting-From-Each-Level Adventure Scoring

Given arrays layers and energy of length n and initial energy K: starting at level i with energy K, for each level j from i upward you first pay layers[j] energy; if the remaining energy is >= energy[j] you pass (gain 1 point), otherwise the run stops. Energy must not go negative.

Goal: return score[i] = number of consecutive levels passed starting from level i.

Constraints

• 1 <= n
• energy must remain >= 0 after paying each layer cost
• K >= 0

Examples

Example 1

Input: ([1,2,1], [0,0,0], 3)
Output: [2, 2, 1]

Explanation: From 0: 3-1=2 pass, 2-2=0 pass, 0-1<0 stop -> 2. From 1: pass two. From 2: pass one.

Example 2

Input: ([2,3], [1,1], 5)
Output: [1, 1]

Explanation: From 0: 5-2=3>=1 pass, 3-3=0<1 stop -> 1. From 1: 5-3=2>=1 pass -> 1.

Hints

1. For each starting level i, simulate forward: subtract layers[j], stop if energy goes negative.
2. After paying, you pass only if the remaining energy is at least energy[j]; otherwise the run halts immediately.
3. Count the consecutive passes from i; the straightforward double loop is O(n^2).

Assign Tasks With Exactly k for Person 1

There are n tasks. Task i gives reward1[i] if done by person 1, or reward2[i] if done by person 2. Person 1 must do exactly k tasks and person 2 does the rest.

Goal: maximize total reward and return it.

Start from giving every task to person 2 (sum(reward2)), then moving task i to person 1 changes the total by reward1[i] - reward2[i]. Pick the k largest such deltas.

Constraints

• 0 <= k <= n
• rewards may be any integers

Examples

Example 1

Input: ([3,2,1], [1,2,3], 1)
Output: 8

Explanation: Base sum(reward2)=6; deltas [2,0,-2], take the top one (2): 6+2=8.

Example 2

Input: ([1,1], [1,1], 2)
Output: 2

Explanation: All deltas 0; total stays at the base 2.

Hints

1. Assign every task to person 2 first; the baseline total is sum(reward2).
2. Reassigning task i to person 1 changes the total by exactly reward1[i] - reward2[i].
3. To honor the 'exactly k' constraint while maximizing, pick the k largest deltas (even if some are negative).

Palindromic Downward Paths in a Tree

You are given a tree of treeNodes nodes (0..treeNodes-1) rooted at node 0, with lowercase labels in string nodes. Edges come as parallel arrays nodeFrom, nodeTo (undirected). A downward path ending at node u and starting at an ancestor a on the root-to-u path is palindromic-rearrangeable if its letters can form a palindrome (at most one letter has odd count).

Goal: for each query node q, return how many ancestors a (including q itself) make the path a -> ... -> q palindromic-rearrangeable.

Encode each path's letter parities as a 26-bit mask; a path is rearrangeable iff its mask has at most one set bit.

Constraints

• 1 <= treeNodes
• labels are lowercase a-z
• edges given as undirected pairs forming a tree rooted at 0

Examples

Example 1

Input: (3, 'aba', [0,1], [1,2], [0,1,2])
Output: [1, 1, 2]

Explanation: Node 2 path a-b-a: paths ending at 2 that rearrange to a palindrome are 'a' (just node 2) and 'aba' (the whole path), giving 2.

Example 2

Input: (1, 'a', [], [], [0])
Output: [1]

Explanation: Single node, the length-1 path is trivially a palindrome.

Hints

1. Represent the multiset of letters on a path by a 26-bit parity mask; the path can be rearranged into a palindrome iff the mask has 0 or 1 bits set (mask & (mask-1) == 0).
2. Let pref[v] be the XOR of label bits from root to v. The path from ancestor a down to q has mask pref[q] XOR pref[parent(a)].
3. During a DFS down to q, the candidate parent(a) masks are exactly the prefix masks of q's ancestors plus a virtual 0 for the root's parent; count how many make pref[q] XOR mask a near-power-of-two.

Solution

This set contains 13 independent tasks. Each section gives the key insight, a correct algorithm with complexity, clean Python, and the edge cases that trip people up. All solutions assume 0-based indexing unless the problem states otherwise.

---

1) Minimum operations to reduce n to 0

Insight. Each operation adds or subtracts a single power of two. Working in binary, we process n from the least-significant bit. A run of 1s is cheaper to clear by adding 1 at the bottom (turning a trailing block of 1s into a single higher 1, i.e. one carry) than by subtracting each 1 individually. The classic decision rule:

• If the current bit is 0, just shift right (no cost) — the bit is already clean.
• If the current bit is 1, look at the next bit up to decide between subtracting 1 (cost 1, clears an isolated 1) and adding 1 (cost 1, collapses a run ...0111 into ...1000, which is fewer total ops).

Concretely, inspect n % 4:

• n % 4 == 1 → the 1 is isolated (...01), subtract 1.
• n % 4 == 3 → start/middle of a run (...11), add 1 to trigger a carry.

Either way we spend one operation and then shift past the now-zero bit.

def min_operations(n: int) -> int:
    ops = 0
    while n:
        if n % 2 == 0:        # bottom bit clean, shift it off for free
            n >>= 1
        elif n % 4 == 3:      # run of 1s -> add 1 (carry), collapses the run
            n += 1
            ops += 1
        else:                 # n % 4 == 1, isolated 1 -> subtract 1
            n -= 1
            ops += 1
    return ops

• Why n % 4 == 3 adds: subtracting would clear one 1 but leave the rest of the run; adding turns 0111 into 1000, replacing many cleanups with a single carry that we handle higher up.
• Edge case for "must keep n >= 0": the greedy above can momentarily increase n via the carry, but it never goes below 0, so the non-negativity constraint is respected. The only decreasing step is the n -= 1 branch, which fires when n % 4 == 1 (so n >= 1), and the n += 1 carry branch only raises n; neither can produce a negative value.
• Complexity: $O(\log n)$ time, $O(1)$ space. This equals the minimum number of operations because each chosen op resolves at least one bit and the run-collapsing rule is provably optimal (it minimizes the count of nonzero "signed-bit" digits — the non-adjacent form).

---

2) Shortest subarray with at least k distinct integers

Insight. Sliding window. Expand the right edge; once the window holds >= k distinct values, shrink from the left as far as possible while still keeping >= k distinct, recording the smallest width seen.

from collections import defaultdict

def shortest_good_subarray(arr, k):
    if k <= 0:
        return 0
    count = defaultdict(int)
    distinct = 0
    best = float('inf')
    left = 0
    for right, x in enumerate(arr):
        if count[x] == 0:
            distinct += 1
        count[x] += 1
        while distinct >= k:                 # window is good -> try to shrink
            best = min(best, right - left + 1)
            y = arr[left]
            count[y] -= 1
            if count[y] == 0:
                distinct -= 1
            left += 1
    return best if best != float('inf') else -1

• No-answer case: if the whole array has fewer than k distinct values, the window never reaches distinct == k, so best stays infinite and we return -1.
• Why shrinking is safe: the answer is monotone — if [l, r] is good, no shorter window ending at r can have more distinct values than this one, so greedily contracting the left edge finds the shortest window ending at each r.
• Complexity: $O(n)$ time (each index enters and leaves the window once), $O(\min(n, U))$ space for the counter.

---

3) First discount to the right (next <= price)

Insight. "First element to the right that is <= prices[i]" is a monotonic stack problem (next-smaller-or-equal element). Keep a stack of indices whose discount is still unknown; when a new price arrives, it resolves everything on the stack that is >= it.

def first_discount(prices):
    n = len(prices)
    final = prices[:]                 # default: full price
    stack = []                        # indices awaiting a discount
    for j in range(n):
        while stack and prices[j] <= prices[stack[-1]]:
            i = stack.pop()
            final[i] = prices[i] - prices[j]
        stack.append(j)
    # whatever remains on the stack never found a j -> sold at full price
    full_price_indices = sorted(stack)
    total = sum(final)
    return total, " ".join(map(str, full_price_indices))

• <= vs <: because the rule is prices[j] <= prices[i], the stack pop condition must also be <= so equal-priced neighbours resolve correctly.
• Full-price items: exactly the indices left on the stack at the end (no smaller-or-equal element to their right). They are already in increasing index order on the stack, but sorting makes the contract explicit; return "" when the stack is empty.
• Complexity: $O(n)$ time, $O(n)$ space — each index is pushed and popped at most once.

---

4) Balanced prefixes in a permutation

Insight. A subarray is a permutation of 1..k iff the positions of values 1..k occupy a contiguous block of length exactly k. So track the min and max position among values 1..k; k is balanced exactly when maxPos - minPos + 1 == k. Process k from 1 to n incrementally so positions are added one at a time.

def balanced_prefixes(p):
    n = len(p)
    pos = [0] * (n + 1)               # pos[v] = index where value v sits
    for i, v in enumerate(p):
        pos[v] = i
    res = []
    lo = float('inf')
    hi = float('-inf')
    for k in range(1, n + 1):
        lo = min(lo, pos[k])
        hi = max(hi, pos[k])
        res.append('1' if hi - lo + 1 == k else '0')
    return ''.join(res)

• Why the span test works: values 1..k are k distinct elements. If they span exactly k consecutive positions, no other value can sit between them (the block has width k and holds k of them), so that block is a permutation of 1..k. If the span exceeds k, some larger value is wedged in and no good subarray exists.
• k = 1 is always '1' (a single element 1 is a permutation of {1}); k = n is always '1' (the whole array).
• Complexity: $O(n)$ time, $O(n)$ space.

---

5) Elevator + stairs: minimize time difference

Insight. For a fixed x (elevator floors), the times are fully determined:

• T_elevator(x) = x * t1.
• T_stairs(x): start with curr = x * e1, walk n - x floors; floor cost is ceil(c / curr), then curr -= e2. Infeasible if curr would go negative before a remaining floor is climbed (energy must stay >= 0, and ceil(c / curr) is undefined when curr == 0).

We want min over feasible x of |T_elevator(x) - T_stairs(x)|. As x grows, T_elevator increases (more elevator floors) and T_stairs decreases (fewer, cheaper stair floors). The difference T_elevator - T_stairs is therefore monotonically increasing in x, so the absolute value is unimodal — we can binary-search for the crossover. A clean and robust implementation simply evaluates every feasible x:

import math

def min_time_diff(n, e1, t1, e2, c):
    best = float('inf')
    for x in range(0, n + 1):
        t_elev = x * t1
        curr = x * e1
        t_stairs = 0
        feasible = True
        for _ in range(n - x):
            if curr <= 0:                # cannot climb: energy non-positive
                feasible = False
                break
            t_stairs += math.ceil(c / curr)
            curr -= e2                   # energy after climbing this floor
            if curr < 0:                 # energy must never go negative
                feasible = False
                break
        if feasible:
            best = min(best, abs(t_elev - t_stairs))
    return best if best != float('inf') else -1

• Binary-search optimization: because diff(x) = T_elevator(x) - T_stairs(x) is monotone increasing, binary-search for the smallest x with diff(x) >= 0, then check that x and x-1 (the sign change straddles the optimum). That cuts the outer loop to $O(\log n)$ evaluations:

def min_time_diff_bsearch(n, e1, t1, e2, c):
    def diff(x):                         # returns (feasible, t_elev - t_stairs)
        curr = x * e1
        t_stairs = 0
        for _ in range(n - x):
            if curr <= 0:
                return (False, None)
            t_stairs += math.ceil(c / curr)
            curr -= e2
            if curr < 0:
                return (False, None)
        return (True, x * t1 - t_stairs)

    lo, hi = 0, n
    best = float('inf')
    while lo <= hi:
        mid = (lo + hi) // 2
        ok, d = diff(mid)
        if not ok:
            # higher x leaves more elevator energy / fewer stairs -> feasible
            lo = mid + 1
            continue
        best = min(best, abs(d))
        if d == 0:
            return 0
        if d > 0:
            hi = mid - 1                 # elevator too long, reduce x
        else:
            lo = mid + 1                 # stairs too long, increase x
    return best if best != float('inf') else -1

• Feasibility direction: larger x means more starting energy and fewer stair floors, so feasibility is also monotone — if some x is infeasible because of low energy, increasing x helps. Probe carefully and keep the full-scan version as the reference; both should agree.
• Edge cases: x = n means take the elevator all the way (T_stairs = 0); x = 0 means walk everything with starting energy 0, which is infeasible whenever n > 0 (cannot compute ceil(c/0)).
• Complexity: full scan $O(n^2)$ worst case ($O(n)$ values of x, $O(n)$ stairs each); binary-search variant $O(n \log n)$.

---

6) Maximum score to reach the end with special jumps

Insight. A standard DP over indices: dp[i] = best score reachable at index i. The allowed step lengths are {1} ∪ {primes whose last digit is 3} = {1, 3, 13, 23, 43, 53, 73, 83, 103, ...}. Precompute the valid jump lengths up to n, then relax dp.

def max_score_special_jumps(arr):
    n = len(arr)
    if n == 0:
        return -1

    def is_prime(num):
        if num < 2:
            return False
        if num % 2 == 0:
            return num == 2
        i = 3
        while i * i <= num:
            if num % i == 0:
                return False
            i += 2
        return True

    # allowed step lengths: 1, plus primes ending in digit 3
    jumps = [1]
    for d in range(3, n, 10):          # 3, 13, 23, ... all end in 3
        if is_prime(d):
            jumps.append(d)

    NEG = float('-inf')
    dp = [NEG] * n
    dp[0] = arr[0]
    for i in range(1, n):
        for j in jumps:
            prev = i - j
            if prev >= 0 and dp[prev] != NEG:
                dp[i] = max(dp[i], dp[prev] + arr[i])
    return dp[-1] if dp[-1] != NEG else -1

• Key correction to a common bug: the jump set is not "every prime index" and not "every prime number" — it is specifically integers of the form 10t + 3 that are also prime. Generating range(3, n, 10) and filtering by primality gives exactly {3, 13, 23, 43, ...} (note 33 = 3·11 and 63 = 9·7 are excluded). The "ends in 3" restriction is enforced entirely by the loop step (range(3, n, 10)), so is_prime only checks primality. Its num % 2 == 0 branch returns num == 2, which correctly keeps the odd value 3 prime — 3 is never rejected by the even-number check.
• Forward vs backward relaxation: here dp[i] pulls from dp[i - j], which is correct because every source index is smaller and already finalized.
• Unreachable end: if dp[n-1] stays -inf, return -1.
• Complexity: $O(n \cdot J)$ where J is the number of valid jump lengths <= n (roughly $O(n / \log n)$ by the prime density, so about $O(n^2 / \log n)$ worst case). Precomputing primes with a sieve makes the jump generation $O(n \log \log n)$.

---

7) Choose a root to minimize edge reversals

Insight. This is LeetCode-1466-style rerooting. Build the underlying tree, marking each undirected edge with whether its original direction matches "parent → child" or not.

1. Root at node 0, DFS once to compute cost[0] = number of edges that point the wrong way (toward the root) when 0 is root.
2. Reroot in a second DFS: moving the root from u to a neighbour v flips exactly the edge u–v. If that edge originally pointed u → v (correct for root u), it becomes wrong, so cost[v] = cost[u] + 1. If it originally pointed v → u, it becomes correct, so cost[v] = cost[u] - 1.
3. Return any node achieving the minimum cost.

from collections import defaultdict
import sys

def best_root_min_reversals(n, edges):
    sys.setrecursionlimit(10 ** 6)
    # adj[u] = list of (v, w) where w = 1 if a reversal is needed to make u->v
    adj = defaultdict(list)
    for u, v in edges:                 # edge originally directed u -> v
        adj[u].append((v, 0))          # u->v already away from u: no cost
        adj[v].append((u, 1))          # traversing v->u is against direction

    cost = [0] * n

    def dfs_count(node, parent):
        total = 0
        for nxt, w in adj[node]:
            if nxt != parent:
                total += w + dfs_count(nxt, node)
        return total

    cost[0] = dfs_count(0, -1)

    def dfs_reroot(node, parent):
        for nxt, w in adj[node]:
            if nxt == parent:
                continue
            # moving root node->nxt: w==0 means edge was node->nxt (now wrong) -> +1
            #                        w==1 means edge was nxt->node (now right) -> -1
            cost[nxt] = cost[node] + (1 if w == 0 else -1)
            dfs_reroot(nxt, node)

    dfs_reroot(0, -1)

    best_node, best_cost = 0, cost[0]
    for i in range(n):
        if cost[i] < best_cost:
            best_node, best_cost = i, cost[i]
    return best_node

• Edge orientation bookkeeping is the whole problem. Store with each undirected edge a flag for whether walking it in the DFS direction agrees with the original arrow; the reroot delta is +1/-1 of exactly the flipped edge.
• Iterative DFS is advisable for very deep trees to avoid recursion limits, but the recursion-limit bump above suffices for typical interview constraints.
• Complexity: $O(n)$ time and space (two linear DFS passes).

---

8) Purchase optimization queries (consecutive buying from a position)

Insight. Buying consecutively to the right with a budget is "longest prefix of the suffix whose sum <= amount". Build a prefix-sum array; for query (pos, amount) with 0-based start s = pos - 1, find the largest end with prefix[end] - prefix[s] <= amount, i.e. prefix[end] <= amount + prefix[s]. Because prices are non-negative, prefix is non-decreasing, so binary-search the boundary.

from bisect import bisect_right

def purchase_queries(prices, queries):
    n = len(prices)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + prices[i]

    res = []
    for pos, amount in queries:
        s = pos - 1
        target = amount + prefix[s]
        # largest index in prefix whose value is <= target (whole array scan)
        end = bisect_right(prefix, target) - 1
        res.append(end - s)            # number of items bought
    return res

• Prerequisite for binary search: prices must be non-negative so the prefix array is monotone. If prices can be negative, fall back to a two-pointer / sliding-window scan per query, or precompute differently.
• Off-by-one: bisect_right(prefix, target) - 1 searches the entire prefix array, not a sub-range. Correctness relies on two facts instead of any explicit [s, n] restriction: prefix is non-decreasing (non-negative prices), and prefix[s] <= target always holds because target = amount + prefix[s] with amount >= 0. Together these guarantee end >= s, so subtracting the start s yields a count that is never negative.
• Complexity: $O(n)$ preprocessing, $O(\log n)$ per query.

---

9) Longest subsequence with sum limit (multiple queries)

Insight. To maximize how many elements you can pick with sum <= q, always take the smallest elements first. Sort nums ascending, take the prefix sums, then for each query binary-search the longest prefix whose sum stays within q. The answer for a query is that prefix length (subsequence order is irrelevant, so contiguity of the sorted prefix is fine).

from bisect import bisect_right

def longest_subseq_with_limit(nums, queries):
    nums = sorted(nums)
    prefix = []
    running = 0
    for x in nums:
        running += x
        prefix.append(running)         # prefix[i] = sum of i+1 smallest
    return [bisect_right(prefix, q) for q in queries]

• Why greedy-smallest is optimal: for a fixed count m, the minimum possible sum is the m smallest elements; if even that exceeds q, no size-m subsequence fits. So the max feasible count is the longest sorted prefix within budget.
• bisect_right(prefix, q) directly returns the count of prefix sums <= q, which is the answer length; works for q smaller than every element (returns 0).
• Assumes non-negative nums (prefix monotone). With negatives, you would always include all negatives first, then add smallest positives — adjust the greedy accordingly.
• Complexity: $O(n \log n)$ to sort, $O(\log n)$ per query.

---

10) Maximize pipeline throughput under scaling budget

Insight. End-to-end throughput is min_i throughput[i], so we are "raising the floor". Binary-search the answer T: to make every service reach at least T, the cost is sum over i of max(0, T - throughput[i]) * scalecost[i]. This cost is monotone in T, so binary-search the largest T whose cost is <= budget.

def max_pipeline_throughput(throughput, scalecost, budget):
    if not throughput:
        return 0

    def cost_to_reach(T):
        total = 0
        for tp, sc in zip(throughput, scalecost):
            if tp < T:
                total += (T - tp) * sc
                if total > budget:     # early exit, avoids overflow blowups
                    return total
        return total

    lo = min(throughput)               # already achievable for free
    hi = lo + budget                   # cannot exceed even if cheapest cost is 1
    ans = lo
    while lo <= hi:
        mid = (lo + hi) // 2
        if cost_to_reach(mid) <= budget:
            ans = mid                  # affordable, try higher
            lo = mid + 1
        else:
            hi = mid - 1               # too expensive, lower the target
    return ans

• Upper bound: raising the floor by one unit costs at least 1 * (cheapest scalecost); a safe, simple hi is min(throughput) + budget (valid when every scalecost >= 1). If costs can be 0, throughput is effectively unbounded for those services — handle that as a special case.
• Only the bottleneck matters: services already at or above T cost nothing, so the check only pays for services below T.
• Complexity: $O(m \log(\text{range}))$ where the range is roughly budget.

---

11) Starting-from-each-level adventure scoring

Insight. Starting at level i with energy K, you pass level j (for j = i, i+1, ...) iff, after paying all of layers[i..j], the remaining energy is still >= energy[j]. Define prefix sums P[j] = layers[0] + ... + layers[j-1]. Starting at i, before attempting j you have spent P[j] - P[i], so:

$K - (P[j] - P[i]) \ge \text{energy}[j] \iff K + P[i] \ge \text{energy}[j] + P[j].$

Let power(i) = K + P[i] (non-decreasing in i) and bar(j) = energy[j] + P[j] — wait, be careful with the exact prefix boundary: paying layers[j] happens before the check, so the spend up to and including level j is P[j+1] - P[i]. The clean form is K + P[i] >= energy[j] + P[j+1]. Define:

• power(i) = K + P[i] — strictly non-decreasing as i increases (more skipped levels = more "saved" budget).
• bar(j) = energy[j] + P[j+1] — a fixed threshold per level.

You pass level j from start i iff power(i) >= bar(j), and the run stops at the first j that fails. Because power(i) only grows with i, the set of passable levels only extends rightward as the start moves right — a monotone two-pointer computes all answers in linear time.

def adventure_scores(layers, energy, K):
    n = len(layers)
    P = [0] * (n + 1)
    for i in range(n):
        P[i + 1] = P[i] + layers[i]
    bar = [energy[j] + P[j + 1] for j in range(n)]

    res = [0] * n
    right = 0                          # furthest reachable boundary so far
    for i in range(n):
        power = K + P[i]
        if right < i:
            right = i                  # cannot pass a level before the start
        while right < n and power >= bar[right]:
            right += 1
        res[i] = right - i             # consecutive levels passed
    return res

• Why the pointer never resets backward: power(i) is non-decreasing in i, so a level passable from start i is also passable from any later start (its power is >=). Thus right is monotone and total work is $O(n)$.
• Boundary if right < i: you cannot count levels to the left of your start; the pointer must never lag the start index.
• Complexity: $O(n)$ time, $O(n)$ space (a brute-force $O(n^2)$ restart-per-start also works but is slower).

---

12) Assign tasks to two people with exactly k tasks for person 1

Insight. Start by giving every task to person 2: baseline sum(reward2). Reassigning task i to person 1 changes the total by diff[i] = reward1[i] - reward2[i]. We must reassign exactly k tasks, and to maximize the total we pick the k largest diff values (even if some are negative — we're forced to take k, so take the least bad ones).

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

• "Exactly k" is the subtlety: if it were "at most k" you would only add positive diffs. Because it's exact, you must include the top k diffs regardless of sign — they minimize the loss when person 1 is worse.
• k = 0 → diffs[:0] is empty, total is sum(reward2); k = n → person 1 does everything, total is sum(reward1).
• Worked example: reward1 = [5,3,4], reward2 = [2,5,1], k = 2. Diffs = [3, -2, 3] → sorted [3, 3, -2]; base = 8; top 2 → 8 + 6 = 14 (person 1 takes tasks 0 and 2).
• Complexity: $O(n \log n)$ for the sort; can be $O(n)$ with a partial selection (heapq.nlargest).

---

13) Count palindromic downward paths ending at queried nodes

Insight. A multiset of letters can form a palindrome iff at most one letter has an odd count. Encode the parity of each of the 26 letters as a 26-bit mask via XOR. For a root-to-u path, let mask(u) be the XOR of letter-bits from the root down to u. The letters on a sub-path a → ... → u (where a is an ancestor) have parity mask(u) XOR mask(parent(a)). Such a path is palindrome-rearrangeable iff that XOR is 0 (all even) or a power of two (exactly one odd letter).

Do one DFS from the root. Maintain a running count of ancestor masks seen on the current root-to-node path (prefix_counts). At node u with mask m, the number of valid downward paths ending at u is:

prefix_counts[m] (XOR 0) plus, for each letter bit b, prefix_counts[m XOR (1<<b)] (exactly one odd letter).

Seed the map with {0: 1} so paths starting at the root itself are counted (the "parent of root" has empty mask 0). Use backtracking: add m before recursing into children, remove it after.

from collections import defaultdict
import sys

def count_palindrome_paths(tree_nodes, nodes, node_from, node_to, queries):
    sys.setrecursionlimit(10 ** 6)
    adj = defaultdict(list)
    for u, v in zip(node_from, node_to):
        adj[u].append(v)
        adj[v].append(u)

    ans = [0] * tree_nodes
    prefix_counts = defaultdict(int)
    prefix_counts[0] = 1               # virtual parent of root: empty mask

    def dfs(u, parent, mask):
        mask ^= (1 << (ord(nodes[u]) - ord('a')))
        # count ancestors a (incl. u) making path a..u palindrome-rearrangeable
        cnt = prefix_counts[mask]                       # XOR == 0 (all even)
        for b in range(26):                             # XOR is a single bit
            cnt += prefix_counts[mask ^ (1 << b)]
        ans[u] = cnt

        prefix_counts[mask] += 1                        # expose u to its subtree
        for w in adj[u]:
            if w != parent:
                dfs(w, u, mask)
        prefix_counts[mask] -= 1                        # backtrack

    dfs(0, -1, 0)
    return [ans[q] for q in queries]

• Why the mask-XOR trick works: parity is all that matters for palindrome-rearrangeability, and XOR of bit-masks tracks per-letter parity in $O(1)$. The "at most one odd letter" condition becomes "the path's combined mask is 0 or has exactly one set bit", checked with 27 lookups (one for zero plus 26 single-bit flips).
• Counting ancestors, not arbitrary paths: because we only look up masks currently on the active root-to-u path (kept correct by add-before-recurse / remove-after), every match corresponds to a genuine ancestor a, exactly as the problem requires.
• Worked example: nodes = ['z','a','a','a'], edges 0-1, 0-2, 1-3, query node 3. Path root→3 is z,a,a; the valid ancestor starts are a=3 ({a}), a=1 ({a,a}), and a=0 ({z,a,a} → one odd z) — all rearrange to palindromes → answer 3.
• Complexity: $O(26 \cdot \text{treeNodes})$ time, $O(\text{treeNodes})$ space. Convert to an explicit stack for very deep trees.

---

Cross-cutting interview notes

• Pattern map: sliding window (#2), monotonic stack (#3), prefix-sum + binary search (#8, #9), binary search on the answer (#5, #10), greedy + sort (#9, #12), DP (#6), tree rerooting (#7), DFS + bitmask parity (#13), two-pointer monotonicity (#11). Naming the pattern out loud earns credit fast in an Uber-style screen.
• Always validate assumptions before binary-searching a prefix: #8 and #9 rely on non-negative values for monotone prefix sums; flag that to the interviewer and fall back to linear scans if negatives are allowed.
• State complexity for every part and call out the precise edge cases (empty input, unreachable end, infeasible elevator, k = 0 / k = n) — that breadth is what distinguishes a strong multi-problem screen answer.