Solve four OA algorithm problems

You are given four independent coding questions.

1) Count square subgrids (multiple queries)

For each query, you are given two integers R and C representing an R × C grid of unit cells.

Return the total number of axis-aligned square subgrids (of all possible side lengths) that can be formed inside the grid.

• Input: q queries, each query contains R, C .
• Output: For each query, output the number of square subgrids.
• Constraints (typical): 1 ≤ q ≤ 2e5 , 1 ≤ R, C ≤ 1e9 .

2) Minimum adjacent swaps to make a palindrome

You are given a string s of length n (in the OA it may be a binary string such as only 'O' and 'I', but assume it can be any characters).

In one move, you may swap two adjacent characters.

Return the minimum number of adjacent swaps needed to rearrange s into a palindrome.

• If it is impossible to form a palindrome, return -1 .

3) Row-major grid walk with obstacles, teleports, and loop detection

You are given an n × m grid. You start at the top-left cell (0,0) and want to reach the bottom-right cell (n-1,m-1).

Movement rule (row-major walk):

• From (r,c) , your next step is normally:
  • (r, c+1) if c+1 < m
  • otherwise wrap to the start of the next row (r+1, 0) if r+1 < n

Additional rules:

• Some cells are blocked (obstacles). If you ever step onto a blocked cell, stop and return -1 .
• Some cells are teleporters . If you step onto a teleporter cell, you are immediately moved to its paired destination cell.
  • Treat teleporting as part of the same “step”: each transition (including landing on a teleporter and being transported) counts as one step total .
• If the process enters a cycle and will never reach the target, return -2 .

Return the number of steps to reach (n-1,m-1) if reachable.

4) Longest subarray under a prefix-sum inequality

You are given an array a of length n (assume a[i] ≥ 0) and an integer k.

Let prefix sums be:

• pref[0] = 0
• pref[i+1] = pref[i] + a[i]

Find the maximum length of a subarray [l, r) (with 0 ≤ l < r ≤ n) such that:

$\text{pref}[r] - 2\cdot\text{pref}[l] \le k$

Return this maximum length.