# Maximum Profit of Operating a Centennial Wheel
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-profit-of-operating-a-centennial-wheel)
Canonical: https://scaleengineer.com/dsa/problems/maximum-profit-of-operating-a-centennial-wheel
**Data structures:** Array
**Companies:** [peak6](https://scaleengineer.com/companies/peak6)
---
## Problem
You are the operator of a Centennial Wheel that has **four gondolas**, and each gondola has room for **up** **to** **four people**. You have the ability to rotate the gondolas **counterclockwise**, which costs you `runningCost` dollars.

You are given an array `customers` of length `n` where `customers[i]` is the number of new customers arriving just before the `ith` rotation (0-indexed). This means you **must rotate the wheel** `i` **times before the** `customers[i]` **customers arrive**. **You cannot make customers wait if there is room in the gondola**. Each customer pays `boardingCost` dollars when they board on the gondola closest to the ground and will exit once that gondola reaches the ground again.

You can stop the wheel at any time, including **before** **serving** **all** **customers**. If you decide to stop serving customers, **all subsequent rotations are free** in order to get all the customers down safely. Note that if there are currently more than four customers waiting at the wheel, only four will board the gondola, and the rest will wait **for the next rotation**.

Return _the minimum number of rotations you need to perform to maximize your profit._ If there is **no scenario** where the profit is positive, return `-1`.

**Example 1:**

![](https://assets.glich.co/dsa/maximum-profit-of-operating-a-centennial-wheel/image0.png) 

**Input:** customers = [8,3], boardingCost = 5, runningCost = 6
**Output:** 3
**Explanation:** The numbers written on the gondolas are the number of people currently there.
1. 8 customers arrive, 4 board and 4 wait for the next gondola, the wheel rotates. Current profit is 4 * $5 - 1 * $6 = $14.
2. 3 customers arrive, the 4 waiting board the wheel and the other 3 wait, the wheel rotates. Current profit is 8 * $5 - 2 * $6 = $28.
3. The final 3 customers board the gondola, the wheel rotates. Current profit is 11 * $5 - 3 * $6 = $37.
The highest profit was $37 after rotating the wheel 3 times.

**Example 2:**

**Input:** customers = [10,9,6], boardingCost = 6, runningCost = 4
**Output:** 7
**Explanation:**
1. 10 customers arrive, 4 board and 6 wait for the next gondola, the wheel rotates. Current profit is 4 * $6 - 1 * $4 = $20.
2. 9 customers arrive, 4 board and 11 wait (2 originally waiting, 9 newly waiting), the wheel rotates. Current profit is 8 * $6 - 2 * $4 = $40.
3. The final 6 customers arrive, 4 board and 13 wait, the wheel rotates. Current profit is 12 * $6 - 3 * $4 = $60.
4. 4 board and 9 wait, the wheel rotates. Current profit is 16 * $6 - 4 * $4 = $80.
5. 4 board and 5 wait, the wheel rotates. Current profit is 20 * $6 - 5 * $4 = $100.
6. 4 board and 1 waits, the wheel rotates. Current profit is 24 * $6 - 6 * $4 = $120.
7. 1 boards, the wheel rotates. Current profit is 25 * $6 - 7 * $4 = $122.
The highest profit was $122 after rotating the wheel 7 times.

**Example 3:**

**Input:** customers = [3,4,0,5,1], boardingCost = 1, runningCost = 92
**Output:** -1
**Explanation:**
1. 3 customers arrive, 3 board and 0 wait, the wheel rotates. Current profit is 3 * $1 - 1 * $92 = -$89.
2. 4 customers arrive, 4 board and 0 wait, the wheel rotates. Current profit is 7 * $1 - 2 * $92 = -$177.
3. 0 customers arrive, 0 board and 0 wait, the wheel rotates. Current profit is 7 * $1 - 3 * $92 = -$269.
4. 5 customers arrive, 4 board and 1 waits, the wheel rotates. Current profit is 11 * $1 - 4 * $92 = -$357.
5. 1 customer arrives, 2 board and 0 wait, the wheel rotates. Current profit is 13 * $1 - 5 * $92 = -$447.
The profit was never positive, so return -1.

**Constraints:**

* `n == customers.length`
* `1 <= n <= 105`
* `0 <= customers[i] <= 50`
* `1 <= boardingCost, runningCost <= 100`

# Approaches
## Simple Iterative Simulation
This approach directly simulates the process described in the problem. We maintain the number of waiting customers, the current profit, and the number of rotations. We iterate rotation by rotation, updating these values at each step. We also keep track of the maximum profit seen so far and the number of rotations at which it occurred. The simulation continues as long as there are new customers arriving or there are customers still waiting to board.
**Time:** O(N + C/4), where N is the length of the `customers` array and C is the total number of customers. In the worst case, C can be up to N * 50. The total number of loop iterations is proportional to N plus the number of rotations needed to serve all customers. · **Space:** O(1), as we only use a few variables to keep track of the state.
**Pros:** Simple to understand and implement.; Correctly models the problem statement step-by-step.
**Cons:** Can be less performant if the total number of customers is very large, as the simulation loop continues one rotation at a time even after all new customers have arrived.
### Explanation
We use a single `while` loop that continues as long as there are customers arriving (we haven't processed the whole `customers` array) or there are people waiting in line. Inside the loop, each iteration represents one rotation of the wheel.

1.  We increment the rotation count.
2.  If there are new customers scheduled to arrive for this rotation (i.e., we haven't exhausted the `customers` array), we add them to the `waitingCustomers` count.
3.  We determine how many customers can board in this rotation, which is the minimum of the number of waiting customers and the capacity of a gondola (4).
4.  We update the number of `waitingCustomers` by subtracting those who just boarded.
5.  We calculate the profit for this rotation (`boarded * boardingCost - runningCost`) and add it to our `currentProfit`.
6.  We then check if this `currentProfit` is greater than the `maxProfit` found so far. If it is, we update `maxProfit` and store the current number of rotations.
7.  The loop terminates when all customers from the input array have arrived and the waiting line is empty.
8.  Finally, we return the number of rotations that yielded the maximum profit. If the maximum profit was never positive, we return -1.

We use `long` for profit variables to prevent potential integer overflow.

```java
class Solution {
    public int minOperationsMaxProfit(int[] customers, int boardingCost, int runningCost) {
        long waitingCustomers = 0;
        long currentProfit = 0;
        long maxProfit = 0; // Start with 0, as we only care about positive profit
        int rotations = 0;
        int resultRotations = -1;
        int i = 0;

        while (i < customers.length || waitingCustomers > 0) {
            rotations++;
            if (i < customers.length) {
                waitingCustomers += customers[i];
                i++;
            }

            long board = Math.min(waitingCustomers, 4);
            waitingCustomers -= board;

            currentProfit += board * boardingCost - runningCost;

            if (currentProfit > maxProfit) {
                maxProfit = currentProfit;
                resultRotations = rotations;
            }
        }

        return resultRotations;
    }
}
```
### Algorithm
*   Initialize state variables: `waitingCustomers = 0`, `currentProfit = 0`, `maxProfit = 0`, `rotations = 0`, `resultRotations = -1`, and an index `i = 0` for the `customers` array.
*   Use a single `while` loop that continues as long as there are new customers to process (`i < customers.length`) or there are customers waiting in line (`waitingCustomers > 0`).
*   In each iteration, which represents one rotation:
    *   Increment the `rotations` counter.
    *   If `i` is within the bounds of the `customers` array, add the new customers (`customers[i]`) to `waitingCustomers` and increment `i`.
    *   Determine the number of customers to board: `boarded = min(waitingCustomers, 4)`.
    *   Update `waitingCustomers` by subtracting `boarded`.
    *   Calculate the profit for this rotation and add it to `currentProfit`: `currentProfit += boarded * boardingCost - runningCost`.
    *   If `currentProfit` is greater than `maxProfit`, update `maxProfit = currentProfit` and `resultRotations = rotations`.
*   After the loop terminates, return `resultRotations`. If profit never became positive, `maxProfit` would remain `0` and `resultRotations` would remain `-1`.

## Optimized Simulation with Bulk Calculation
This approach improves upon the simple simulation by first processing all customer arrivals in a loop. After this, instead of continuing to loop for any remaining customers, it calculates the profit from serving them in a more direct, mathematical way. This avoids a potentially long loop if there's a large queue of waiting customers.
**Time:** O(N), where N is the length of the `customers` array. The initial simulation runs in O(N), and the post-processing step for any remaining customers takes constant O(1) time. · **Space:** O(1), using only a few variables for state tracking.
**Pros:** More efficient in practice, especially when the total number of customers is much larger than the number of arrival days (N).; Replaces a potentially long loop with constant-time arithmetic operations for remaining customers.
**Cons:** The logic is slightly more complex due to the separation into two phases.
### Explanation
The simulation is split into two phases:

1.  **Initial Phase (during customer arrivals):** We iterate through the `customers` array. In each iteration, we simulate one rotation, adding new customers, boarding up to 4, and updating the profit. We track the maximum profit throughout this phase.

2.  **Post-processing Phase (after all arrivals):** After the initial loop, we might have `waitingCustomers` left. Instead of looping, we calculate the profit from them analytically.
    *   First, we determine if it's even profitable to continue. The best-case profit per rotation is `4 * boardingCost - runningCost`. If this value is not positive, we stop.
    *   If it is profitable, we calculate how many full rotations (boarding 4 customers) we can do with the `waitingCustomers`. We compute the total profit and rotations from these in one step.
    *   We then check if this new profit state gives us a new maximum.
    *   Finally, we handle the last few remaining customers (fewer than 4) with one final rotation and profit calculation, again checking if it results in a new maximum profit.

This two-phase approach is more efficient as it replaces a potentially long loop with a few constant-time arithmetic operations.

```java
class Solution {
    public int minOperationsMaxProfit(int[] customers, int boardingCost, int runningCost) {
        long waitingCustomers = 0;
        long currentProfit = 0;
        long maxProfit = 0;
        int rotations = 0;
        int resultRotations = -1;

        // Phase 1: Process customers as they arrive
        for (int customerCount : customers) {
            rotations++;
            waitingCustomers += customerCount;
            
            long board = Math.min(waitingCustomers, 4);
            waitingCustomers -= board;
            
            currentProfit += board * boardingCost - runningCost;
            
            if (currentProfit > maxProfit) {
                maxProfit = currentProfit;
                resultRotations = rotations;
            }
        }

        // Phase 2: Process remaining waiting customers
        if (waitingCustomers > 0) {
            long profitPerFour = (long)4 * boardingCost - runningCost;
            
            if (profitPerFour > 0) {
                long fullRotations = waitingCustomers / 4;
                currentProfit += fullRotations * profitPerFour;
                rotations += fullRotations;
                
                if (currentProfit > maxProfit) {
                    maxProfit = currentProfit;
                    resultRotations = rotations;
                }
                
                long remainingCustomers = waitingCustomers % 4;
                if (remainingCustomers > 0) {
                    long lastProfit = remainingCustomers * boardingCost - runningCost;
                    currentProfit += lastProfit;
                    rotations++;
                    if (currentProfit > maxProfit) {
                        maxProfit = currentProfit;
                        resultRotations = rotations;
                    }
                }
            }
        }
        
        return resultRotations;
    }
}
```
### Algorithm
*   Initialize state variables: `waitingCustomers = 0`, `currentProfit = 0`, `maxProfit = 0`, `rotations = 0`, `resultRotations = -1`.
*   **Phase 1: Simulation during arrivals.**
    *   Loop through the `customers` array. For each entry `customers[i]`, simulate one rotation.
    *   Increment `rotations`, add `customers[i]` to `waitingCustomers`.
    *   Board up to 4 customers, update `waitingCustomers` and `currentProfit`.
    *   Check if `currentProfit` is a new `maxProfit` and update if necessary.
*   **Phase 2: Post-processing for remaining customers.**
    *   After the loop, check if `waitingCustomers > 0`.
    *   Calculate the profit for a full rotation: `profitPerFour = 4 * boardingCost - runningCost`.
    *   If `profitPerFour <= 0`, it's not profitable to continue, so we stop.
    *   If `profitPerFour > 0`:
        *   Calculate the number of full rotations for the remaining customers: `fullRotations = waitingCustomers / 4`.
        *   Add the bulk profit `fullRotations * profitPerFour` to `currentProfit` and `fullRotations` to `rotations`.
        *   Check for a new `maxProfit`.
        *   Calculate the remaining customers after full rotations: `remaining = waitingCustomers % 4`.
        *   If `remaining > 0`, simulate one final rotation for them, update `currentProfit` and `rotations`, and perform a final check for `maxProfit`.
*   Return `resultRotations`.

# Solutions
### Java

```java
class Solution {
public
  int minOperationsMaxProfit(int[] customers, int boardingCost,
                             int runningCost) {
    int ans = -1;
    int mx = 0, t = 0;
    int wait = 0, i = 0;
    while (wait > 0 || i < customers.length) {
      wait += i < customers.length ? customers[i] : 0;
      int up = Math.min(4, wait);
      wait -= up;
      ++i;
      t += up * boardingCost - runningCost;
      if (t > mx) {
        mx = t;
        ans = i;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minOperationsMaxProfit(vector<int> &customers, int boardingCost,
                             int runningCost) {
    int ans = -1;
    int mx = 0, t = 0;
    int wait = 0, i = 0;
    while (wait || i < customers.size()) {
      wait += i < customers.size() ? customers[i] : 0;
      int up = min(4, wait);
      wait -= up;
      ++i;
      t += up * boardingCost - runningCost;
      if (t > mx) {
        mx = t;
        ans = i;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minOperationsMaxProfit(self, customers: List[int], boardingCost: int, runningCost: int) -> int: ans = - 1 mx = t = 0 wait = 0 i = 0 while wait or i < len(customers): wait += customers[i] if i < len(customers) else 0 up = wait if wait < 4 else 4 wait -= up t += up * boardingCost - runningCost i += 1 if t > mx: mx = t ans = i return ans

```