Below are multiple independent coding problems. --- ## Problem 1: Reduce an integer to 0 with \(\pm 2^i\) You are given a positive integer \(n\). In one operation you may replace \(n\) with \(n + 2^i\) or \(n - 2^i\) for any integer \(i \ge 0\). **Task:** Return the minimum number of operations needed to make \(n = 0\). **Constraints (typical):** \(1 \le n \le 10^{18}\). --- ## Problem 2: Shortest subarray with at least \(k\) distinct integers You are given an integer array `arr` of length \(n\) and an integer \(k\). A subarray is **good** if it contains **at least \(k\)** distinct values. **Task:** Return the length of the shortest good subarray. If no such subarray exists, return `-1`. **Constraints (typical):** \(1 \le n \le 2\times 10^5\). --- ## Problem 3: Apply the first valid discount to the right You are given an array `prices`. For each index `i`, define the discount as the first index `j > i` such that `prices[j] <= prices[i]`. - If such `j` exists: `final[i] = prices[i] - prices[j]` - Otherwise: `final[i] = prices[i]` (sold at full price) **Task:** Output: 1. The **sum** of all final prices. 2. The list of **0-based indices** that are sold at full price, in increasing order. **Constraints (typical):** \(1 \le n \le 2\times 10^5\). --- ## Problem 4: Max-score jump game with special prime jumps You are given an integer array `arr` of length \(n\). You start at index `0` and must end at index `n-1`. From index `i`, you may jump to: - `i + 1`, or - `i + p` where `p` is a **prime number** and `p % 10 == 3` (e.g., 3, 13, 23, 43, ...), and `i + p < n`. Your score is the sum of `arr` values on all visited indices (including start and end). **Task:** Return the maximum achievable score when reaching `n-1`. If `n-1` is unreachable, return `-1`. **Constraints (typical):** \(1 \le n \le 2\times 10^5\), `arr[i]` may be negative. --- ## Problem 5: Count ancestor endpoints whose path can be permuted into a palindrome You are given a rooted tree with nodes `0..n-1` (root is node `0`). Each node has a lowercase letter. Input is provided as: - `treeNodes = n` - `nodes`: a char array of length `n`, where `nodes[i]` is the character on node `i` - `nodeFrom`, `nodeTo`: arrays of length `n-1` describing directed parent→child edges (`nodeFrom[i] -> nodeTo[i]`), forming a tree - `queries`: array of start nodes For each query start node `u`: - Consider all endpoints `v` on the path from `u` up to the root `0` (i.e., `v` can be `u`, its parent, ..., `0`). - Let the multiset of characters on the path `u -> ... -> v` (inclusive) be collected. - This path is counted if its characters can be **rearranged** into a palindrome (i.e., at most one character has an odd frequency). **Task:** For each query `u`, return how many such endpoints `v` exist. **Constraints (typical):** \(n, q \le 2\times 10^5\). --- ## Problem 6: Maximize pipeline throughput under a scaling budget You have \(n\) services connected in a pipeline. The pipeline throughput is: \[ T = \min_i throughput[i] \] You may scale service `i` any number of times. Each scaling: - increases `throughput[i]` by `1` - costs `scale_cost[i]` Given integer `budget`, **total scaling cost** must be \(\le budget\). **Task:** Return the maximum achievable pipeline throughput `T`. **Constraints (typical):** \(n \le 2\times 10^5\), values up to \(10^{18}\). --- ## Problem 7: Elevator-then-stairs with energy-dependent stair time You must go from floor `0` to floor `N`. You may take the elevator first from floor `0` to floor `x` (choose `x` once, `0 <= x <= N`). - For each elevator floor ascended: gain `e1` energy and spend `t1` time. - After elevator: your energy is `E = x * e1`. Then you must climb the remaining `N - x` floors using stairs. For each stair floor: - At the **start** of the floor, if current energy is `E`, the time spent is `ceil(c / E)`. - Then you spend `e2` energy: `E := E - e2`. - Energy may never become negative; if `E < 0` at any step, that choice of `x` is invalid. **Task:** Choose `x` to minimize total time. If no `x` is feasible, return `-1`. **Constraints (typical):** \(1 \le N \le 10^6\), parameters are positive integers. --- ## Problem 8: Assign tasks to two people with exactly \(k\) tasks for person A You have `n` tasks. If task `i` is done by: - person A: reward `reward1[i]` - person B: reward `reward2[i]` Each task must be assigned to exactly one person. Person A must do **exactly `k` tasks**. **Task:** Return the maximum possible total reward. **Constraints (typical):** \(n \le 2000\), \(0 \le k \le n\). --- ## Problem 9: Score from each start index with energy thresholds You are given: - `layers[0..n-1]`: energy cost to attempt/pass level `j` - `energyReq[0..n-1]`: minimum remaining energy needed *after paying the cost* to pass level `j` - initial energy `K` Starting from index `i`: - Set `E = K`. - For `j = i..n-1`: 1. Pay the level cost: `E := E - layers[j]`. If `E < 0`, stop. 2. If `E >= energyReq[j]`, you pass and gain 1 point; otherwise stop (cannot proceed further). **Task:** Return an array `score` of length `n` where `score[i]` is the number of points you can earn starting at level `i`. **Note:** An \(O(n^2)\) solution will time out; design a faster approach. --- ## Problem 10: Buy the maximum number of consecutive items per query You are given `prices[0..n-1]` (positive integers). Each query provides: - `pos` (1-based starting index) - `amount` (budget) From index `start = pos - 1`, you can buy items consecutively to the right while the running sum does not exceed `amount`. **Task:** For each query, return the maximum number of items you can buy. **Constraints (typical):** \(n, q \le 2\times 10^5\). --- ## Problem 11: Minimum edge reversals so every node can reach the chosen root You are given `n` nodes and `n-1` directed edges `edges[i] = [a, b]` meaning `a -> b`. Ignoring direction, the graph is a tree. For each node `r` considered as the root, you may reverse any subset of edges. **Task:** Compute `res[r]` = the minimum number of edge reversals required so that **every node has a directed path to `r`** (equivalently, all edges point toward `r` along the tree). Return `res` for all `r`. **Constraints (typical):** \(n \le 2\times 10^5\). --- ## Problem 12: For each \(w\), do values \(1..w\) occupy a contiguous block? You are given a permutation `perm[0..n-1]` containing each integer from `1` to `n` exactly once. For each window size \(w = 1..n\), define `ans[w] = 1` if the positions of the numbers `{1,2,...,w}` in `perm` form a contiguous subarray (in any order). Otherwise, `ans[w] = 0`. Equivalently, let `pos[x]` be the index where value `x` appears. Then `ans[w] = 1` iff: \[ \max_{1\le x\le w} pos[x] - \min_{1\le x\le w} pos[x] + 1 = w. \] **Task:** Return `ans[1..n]`. **Constraints (typical):** \(n \le 2\times 10^5\).