Solve three C++ algorithmic tasks

Solve the following three C++ algorithmic tasks. For each, implement an efficient function and state time and space complexity.

a) Diminishing prices revenue: Given an array inventory where inventory[i] is the initial sale price for type i, each time you sell one unit of a type, the next sale price for that type decreases by 1 down to 0. You must perform exactly orders sales across all types to maximize total revenue. Return revenue modulo 1_000_000_007. Constraints: 1 <= inventory.size() <= 2e5, 1 <= orders <= 1e13, 1 <= inventory[i] <= 1e9. Target: O(n log max(inventory)) or better.

b) Count subarrays with fixed bounds: Given an integer array nums and two integers minVal and maxVal (minVal <= maxVal), count the number of subarrays whose minimum equals minVal and whose maximum equals maxVal. Constraints: 1 <= nums.size() <= 2e5, -1e9 <= nums[i] <= 1e9. Target: O(n) time, O(1) extra space.

c) Binary matrix row-equivalence under column flips: Given a binary matrix A with n rows and m columns (toggling a column flips that bit in every row), two rows are equivalent if one can be transformed into the other by flipping any subset of columns. Count the number of unordered pairs of equivalent rows. Return a 64-bit integer. Constraints: 1 <= n <= 1e5, 1 <= m <= 30. Target: O(n * m / 64) or better using hashing/bitmasks.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Diminishing Prices Revenue (Maximize Sales Revenue)

Given an array inventory where inventory[i] is the initial sale price for color/type i, each time you sell one unit of a type the next sale price for that type decreases by 1 (down to a minimum of 0). You must perform exactly orders sales across all types to maximize total revenue. Return the maximum total revenue modulo 1_000_000_007.

Greedy idea: always sell from the currently most-expensive type. Sort the prices descending and process them in horizontal 'bands'. With width types currently at price >= the next distinct level, you can sell whole rectangular blocks (an arithmetic series of prices) at once instead of one unit at a time, giving O(n log n) overall.

Constraints: 1 <= inventory.size() <= 2e5, 1 <= orders <= 1e13, 1 <= inventory[i] <= 1e9. Target: O(n log max(inventory)) or better.

Example: inventory = [2,8,4,10,6], orders = 20 -> 110.

Constraints

• 1 <= inventory.size() <= 2e5
• 1 <= orders <= 1e13 (must fit in a 64-bit integer)
• 1 <= inventory[i] <= 1e9
• Return the answer modulo 1_000_000_007

Hints

1. Always sell the most expensive unit available; sort prices descending and peel off the top band.
2. When width types all sit above the next distinct price level, the prices you collect form an arithmetic series — sum it in O(1) with n*(top+bot)/2 instead of looping unit by unit.
3. Watch the partial last band: full_rows = remaining // width complete rows, then remaining % width extra columns each sell one more unit at price (cur - full_rows).
4. Take the modulo only at the end of each block sum; orders up to 1e13 needs a 64-bit type.

Count Subarrays With Fixed Bounds

Given an integer array nums and two integers minVal and maxVal (minVal <= maxVal), count the number of (contiguous) subarrays in which the minimum element equals exactly minVal and the maximum element equals exactly maxVal.

A single linear scan suffices. Track the most recent index where you saw minVal, the most recent index where you saw maxVal, and the most recent index of an out-of-range value (a value < minVal or > maxVal) which acts as a hard left boundary. For each right endpoint i, the number of valid subarrays ending at i is min(lastMin, lastMax) - leftBound when both have been seen since the last boundary, else 0.

Constraints: 1 <= nums.size() <= 2e5, -1e9 <= nums[i] <= 1e9. Target: O(n) time, O(1) extra space.

Example: nums = [1,3,5,2,7,5], minVal = 1, maxVal = 5 -> 2.

Constraints

• 1 <= nums.size() <= 2e5
• -1e9 <= nums[i] <= 1e9
• minVal <= maxVal
• The count can exceed 32-bit range; use a 64-bit accumulator

Hints

1. Any value outside [minVal, maxVal] can never be part of a valid subarray — treat its index as a fresh left boundary and reset state.
2. For a subarray to qualify, it must contain at least one minVal and at least one maxVal; track the latest index of each.
3. Subarrays ending at i are valid only if they start after the boundary and include both the latest minVal and latest maxVal, so the count is min(lastMin, lastMax) - leftBound.
4. When minVal == maxVal, the same element satisfies both conditions simultaneously.

Binary Matrix Row Equivalence Under Column Flips

Given a binary matrix A with n rows and m columns, toggling a column flips that bit in every row. Two rows are considered equivalent if one can be transformed into the other by flipping any subset of columns. Count the number of unordered pairs of equivalent rows.

Key observation: flipping a subset of columns is the same as XOR-ing both rows by the same mask. A row r1 can become r2 iff r1 XOR r2 is achievable by some column mask — which it always is, for the mask equal to r1 XOR r2. But the SAME mask must apply to both rows being compared, so the real equivalence is: r1 and r2 are equivalent iff they are identical OR exact bitwise complements. Normalize every row by flipping the whole row when its first bit is 1 (forcing the leading bit to 0); identical and complementary rows collapse to the same canonical form. Group rows by canonical form and sum c*(c-1)/2 over each group.

Constraints: 1 <= n <= 1e5, 1 <= m <= 30. Return a 64-bit integer. Target: O(nm) (or O(nm/64) with bitmask packing).

Example: A = [[0,1,0],[1,0,1],[0,0,0]] -> 1 (rows 0 and 1 are complements).

Constraints

• 1 <= n <= 1e5
• 1 <= m <= 30 (a row fits in a 32-bit mask)
• Every entry of A is 0 or 1
• Return a 64-bit integer (up to ~n^2/2 pairs)

Hints

1. Flipping a column XORs the same bit across all rows; two rows are reachable from each other only if they are identical or exact complements.
2. Canonicalize each row by XOR-ing it with its own first bit, forcing the leading bit to 0 — identical and complementary rows then map to the same key.
3. Pack the m <= 30 bits into a single integer mask so each row's canonical form is one hashable key.
4. Within each equivalence group of size c, the number of unordered pairs is c*(c-1)/2; sum across groups using a 64-bit accumulator.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

Solve the following three C++ algorithmic tasks. For each, implement an efficient function and state time and space complexity. a) Diminishing prices revenue: Given an array inventory where inventory[i] is the initial sale price for type i, each time you sell one unit of a type, the next sale price for that type decreases by 1 down to 0. You must perform exactly orders sales across all types to maximize total revenue. Return revenue modulo 1_000_000_007. Constraints: 1 <= inventory.size() <= 2e5, 1 <= orders <= 1e13, 1 <= inventory[i] <= 1e9. Target: O(n log max(inventory)) or better. b) Count subarrays with fixed bounds: Given an integer array nums and two integers minVal and maxVal (minVal...

Recommended Approach

Represent each cell as a state. Use BFS for minimum-distance propagation, DFS with memoization for longest monotonic paths, and careful boundary checks for simulation. Store obstacles or visited cells in sets when the grid is sparse.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

A full grid traversal is O(mn) time and O(mn) space in the worst case. Sparse simulation is O(number_of_commands) plus obstacle storage.

Edge Cases and Tests

Empty grid, one row/column, blocked start or target, boundaries, repeated visits, and tie-breaking among equal-distance cells.