Petrol Pump – TCS CodeVita

Minimize the time required to fill petrol in all vehicles using two vending machines

Understand the Problem

Problem Statement

A big group of students, starting a long journey on different vehicles, needs to fill petrol in their vehicles. As a group leader, you must minimize the time they spend at the petrol pump to start the journey as early as possible.

You are given the quantity of petrol (in litres) that can be filled in each vehicle. There are two petrol vending machines at the pump, each dispensing petrol at 1 litre per second. Arrange the vehicles between the two machines to minimize the total time required to fill all vehicles.

Return the shortest possible time in seconds.

Constraints

1 ≤ Number of vehicles < 50
0 ≤ Quantity of petrol required in any vehicle ≤ 200

Examples

Example 1

Input

1 2 3 4 5 10 11 3 6 16

Output

Explanation

Machine 1 fills: 16+6+4+3+2 = 31 seconds. Machine 2 fills: 11+10+5+3+1 = 30 seconds. The total time is max(31,30) = 31 seconds.

Example 2

Input

25 30 35 20 90 110 45 70 80 12 30 35 85

Output

Explanation

Machine 1 fills: 80+45+35+30+25+12+85+20 = 332 seconds. Machine 2 fills: 90+70+35+30+110 = 335 seconds. The total time is max(332,335) = 335 seconds.

Solution

#include <stdio.h>
#include <limits.h>

int main() {
    int petrol[50];
    int n = 0;
    int total = 0;
    
    // Read input
    while (scanf("%d", &petrol[n]) != EOF) {
        total += petrol[n];
        n++;
    }
    
    // DP table: dp[i][j] = can we achieve sum j using first i items?
    int dp[n + 1][total + 1];
    
    // Initialize
    for (int i = 0; i <= n; i++)
        dp[i][0] = 1;
    for (int j = 1; j <= total; j++)
        dp[0][j] = 0;
    
    // Fill DP table
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= total; j++) {
            dp[i][j] = dp[i-1][j];
            if (petrol[i-1] <= j)
                dp[i][j] = dp[i][j] || dp[i-1][j - petrol[i-1]];
        }
    }
    
    // Find the largest sum <= total/2 that we can achieve
    int best = 0;
    for (int j = total / 2; j >= 0; j--) {
        if (dp[n][j]) {
            best = j;
            break;
        }
    }
    
    // The answer is the larger partition
    printf("%d\n", total - best);
    
    return 0;
}

Time:O(n × total) where n is number of vehicles and total is sum of all petrol requirements

Space:O(n × total) for the DP table

Approach:

Step-by-step explanation:

Input Reading: Read all petrol quantities and calculate total sum
DP Initialization: Create a 2D array where dp[i][j] indicates if sum j can be achieved using first i vehicles
Base Cases: dp[i][0] = 1 (sum 0 is always achievable), dp[0][j] = 0 (no items can't achieve positive sum)
DP Filling: For each vehicle, either include it (if capacity allows) or exclude it
Optimal Partition: Find the largest achievable sum ≤ total/2
Result: The time is the larger partition (total - best)

Visual Explanation

Loading diagram...

All Problems