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`.