Find Time Required to Eliminate Bacterial Strains

Find Time Required to Eliminate Bacterial Strains - Problem

You are given an integer array timeReq and an integer splitTime. In the microscopic world of the human body, the immune system faces an extraordinary challenge: combatting a rapidly multiplying bacterial colony that threatens the body's survival.

Initially, only one white blood cell (WBC) is deployed to eliminate the bacteria. However, the lone WBC quickly realizes it cannot keep up with the bacterial growth rate. The WBC devises a clever strategy to fight the bacteria:

The ith bacterial strain takes timeReq[i] units of time to be eliminated.
A single WBC can eliminate only one bacterial strain. Afterwards, the WBC is exhausted and cannot perform any other tasks.
A WBC can split itself into two WBCs, but this requires splitTime units of time.
Once split, the two WBCs can work in parallel on eliminating the bacteria.
Only one WBC can work on a single bacterial strain. Multiple WBCs cannot attack one strain in parallel.

You must determine the minimum time required to eliminate all the bacterial strains. Note that the bacterial strains can be eliminated in any order.

Input & Output

Example 1 — Basic Case

$ Input: timeReq = [4, 2, 6], splitTime = 3

› Output: 6

💡 Note: Start with 1 WBC. Assign strain 6 (time=6), then strain 4 (time=4), then strain 2 to second WBC (time=6). Total time is max(6,4) after optimal splitting = 6.

Example 2 — No Splitting Needed

$ Input: timeReq = [1, 1, 1], splitTime = 10

› Output: 3

💡 Note: Split cost (10) is very high. Better to use single WBC: 1+1+1=3 total time.

Example 3 — Beneficial Splitting

$ Input: timeReq = [10, 10], splitTime = 1

› Output: 11

💡 Note: Split WBC (cost=1), then assign one strain to each WBC: max(1+10, 1+10) = 11. Better than single WBC taking 20 time.

Constraints

1 ≤ timeReq.length ≤ 10⁴
1 ≤ timeReq[i] ≤ 10⁴
1 ≤ splitTime ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Bacterial strains [4,2,6] and split cost 3

Strategy

Decide when to split WBCs vs assign strains directly

Output

Minimum time to eliminate all strains: 6

Key Takeaway

🎯 Key Insight: Balance split costs against parallel work benefits to minimize total completion time

Asked in

G Google 45 a Amazon 38 M Microsoft 32 f Meta 28

This problem requires finding the optimal strategy for WBC splitting and task assignment. The key insight is deciding when splitting cost is justified by parallel work benefits. The greedy approach using priority queues provides an efficient solution with O(n log n) time complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Recursive	O(2^n)	O(n)	Try all possible ways to split and assign bacterial strains
Greedy Priority Queue	O(n log n)	O(n)	Always split the WBC with maximum remaining work time

Brute Force Recursive — Algorithm Steps

Step 1: For current state, try splitting each WBC
Step 2: For each WBC, try eliminating each remaining strain
Step 3: Recursively solve subproblems and return minimum

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

One WBC, all strains remaining

Branch Decisions

For each WBC: split or assign strain

Find Minimum

Return minimum time across all paths

Code -

solution.c — C

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

int max(int a, int b) { return a > b ? a : b; }
int min(int a, int b) { return a < b ? a : b; }

int solve(int* strains, int strainCount, int* wbcs, int wbcCount, int splitTime) {
    if (strainCount == 0) {
        int maxVal = 0;
        for (int i = 0; i < wbcCount; i++) {
            maxVal = max(maxVal, wbcs[i]);
        }
        return maxVal;
    }
    
    int minTime = INT_MAX;
    
    // Try splitting each WBC
    for (int i = 0; i < wbcCount; i++) {
        int* newWbcs = (int*)malloc((wbcCount + 1) * sizeof(int));
        memcpy(newWbcs, wbcs, wbcCount * sizeof(int));
        newWbcs[i] += splitTime;
        newWbcs[wbcCount] = wbcs[i] + splitTime;
        int result = solve(strains, strainCount, newWbcs, wbcCount + 1, splitTime);
        minTime = min(minTime, result);
        free(newWbcs);
    }
    
    // Try eliminating each strain with each WBC
    for (int i = 0; i < strainCount; i++) {
        for (int j = 0; j < wbcCount; j++) {
            int* newStrains = (int*)malloc((strainCount - 1) * sizeof(int));
            int idx = 0;
            for (int k = 0; k < strainCount; k++) {
                if (k != i) newStrains[idx++] = strains[k];
            }
            int* newWbcs = (int*)malloc(wbcCount * sizeof(int));
            memcpy(newWbcs, wbcs, wbcCount * sizeof(int));
            newWbcs[j] += strains[i];
            int result = solve(newStrains, strainCount - 1, newWbcs, wbcCount, splitTime);
            minTime = min(minTime, result);
            free(newStrains);
            free(newWbcs);
        }
    }
    
    return minTime;
}

int solution(int* timeReq, int n, int splitTime) {
    int wbc = 0;
    return solve(timeReq, n, &wbc, 1, splitTime);
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int timeReq[100], n = 0;
    char* ptr = strtok(line + 1, ",]");
    while (ptr != NULL) {
        timeReq[n++] = atoi(ptr);
        ptr = strtok(NULL, ",]");
    }
    
    int splitTime;
    scanf("%d", &splitTime);
    
    printf("%d\n", solution(timeReq, n, splitTime));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

Each strain can be handled by exponentially many WBC configurations

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth proportional to number of strains

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Recursive — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler