Infosys | OA | Minimum Battery Replacements With One Capacity Boost

Minimum Battery Replacements With One Capacity Boost

You are driving an electric vehicle from position 0 to a destination located at position target.

The vehicle starts with a battery that allows it to travel at most startBattery distance.

Along the route, there are n battery replacement stations.

You are given two integer arrays:

• position[i] — the position of the i-th battery station.
• battery[i] — the capacity of the replacement battery available at that station.

When you stop at station i, your current battery is completely removed and replaced with the battery available at that station.

Therefore, after stopping at station i, your new battery capacity becomes exactly:

battery[i]

The unused capacity of your previous battery is lost and cannot be added to the new battery.

You also have a special upgrade that can be used at most once during the journey.

When replacing your battery at a station, you may use this upgrade to double the capacity of the battery installed at that station.

In that case, the new battery capacity becomes:

2 * battery[i]

The upgrade can be used at only one station.

Each battery replacement counts as one stop, whether or not the upgrade is used.

Return the minimum number of stops required to reach target.

If reaching the destination is impossible, return -1.

You do not need to stop if your current battery can directly reach the destination.

---

Example 1

Input:
position = [4, 8, 12]
battery = [5, 6, 4]
startBattery = 7
target = 16

Output:
2

Explanation

Initially, the vehicle is at position 0 with battery capacity 7, so it can reach position 7.

Stop at the station at position 4 and use the special upgrade.

The battery available there has capacity 5, so the upgraded battery has capacity:

2 * 5 = 10

From position 4, the vehicle can now reach position 14.

Therefore, it can reach the station at position 12.

Stop at position 12 and replace the battery normally with capacity 4.

From position 12, the vehicle can reach:

12 + 4 = 16

which is the destination.

The total number of stops is 2.

---

Example 2

Input:
position = [5, 11]
battery = [4, 10]
startBattery = 5
target = 20

Output:
2

Explanation

The vehicle can initially reach the station at position 5.

If the normal battery of capacity 4 is installed there, the vehicle can only reach position 9, so it cannot reach the next station.

Instead, use the special upgrade at position 5.

The new battery capacity becomes:

2 * 4 = 8

The vehicle can now reach position 13, allowing it to reach the station at position 11.

Replace the battery there with capacity 10.

The vehicle can then reach position 21, which is beyond the destination.

Therefore, the minimum number of stops is 2.

---

Example 3

Input:
position = [6, 15]
battery = [5, 10]
startBattery = 5
target = 25

Output:
-1

Explanation

The first battery station is at position 6, but the initial battery only allows the vehicle to reach position 5.

Since no station is reachable, the destination cannot be reached.

---

Example 4

Input:
position = [5, 10]
battery = [5, 5]
startBattery = 20
target = 15

Output:
0

Explanation

The initial battery can directly reach the destination, so no battery replacement is required.

---

Constraints

1 <= position.length == battery.length <= 2000
1 <= position[i] < target
1 <= battery[i] <= 10^9
1 <= startBattery <= 10^9
1 <= target <= 10^9
position is strictly increasing.

---

Function Signature

C++

class Solution {
public:
    int minBatteryStops(
        vector<int>& position,
        vector<int>& battery,
        int startBattery,
        int target
    ) {
        
    }
};

---

Important Clarifications

1. Replacing a battery completely discards the previous battery.

   For example, if the current battery has 3 units remaining and the replacement battery has capacity 10, the new battery capacity is:

10

not:

3 + 10

1. The special upgrade doubles only the battery installed at the station where the upgrade is used.

2. The upgrade can be used at most once.

3. Using the upgrade does not count as an additional stop.

4. Reaching the destination itself does not count as a stop.

5. A station may be skipped if a later station can be reached directly.

6. The vehicle only moves toward the destination.

---

Follow-up

Can you solve the problem in O(n²) time using dynamic programming?

Can you find a more efficient solution for larger constraints?