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.