In this problem, you have M heroes all with the same health H

Heroes vs Villains Battle

In this problem, you have M heroes, all with the same health H. There are N villains, each with their own health Vi.

Infosys HackWithInfy 2025

When a hero, with health H, battles a villain with health Vi, the following scenarios can occur:

• If H > Vi: The villain is defeated, and the hero's health decreases by Vi.
• If H < Vi: The villain wins, the hero's health does not change, and the hero is no longer able to fight.
• If H = Vi: Both the hero and villain are considered defeated, and neither can fight.

The heroes start fighting the villains one by one, in the same order: first villain 1, then villain 2, and so on.

It may be possible that before defeating all the villains, all the heroes are defeated. Therefore, you need to remove some villains from the front to ensure the heroes' victory.

Task:

Your task is to find the minimum number of villains you need to remove from the front such that the victory of the heroes is guaranteed.

Note: If in the last battle, both the hero and villain are defeated, and no more heroes or villains remain, it is still considered a victory since all the villains are defeated.

Input Format:

The input consists of:

1. The first line contains an integer, N, denoting the number of villains. (N :: 1 -> 2*10^5)
2. The second line contains an integer, M, denoting the number of heroes. (M :: 1 -> 2*10^5)
3. The third line contains an integer, H, denoting the health of each of the heroes. (H :: 1 -> 10^9)
4. The next N lines each contain an integer, describing the health of each villain. (array[i] :: 1 -> 10^9)

Case#: 1

Example Input:

4
4
3
3
1
3
3
   

Output Format:

Print the minimum number of villains you need to remove from the front to guarantee the heroes' victory.

Output:

0

[3, 1, 3, 3]. We have 4 heroes will health 3. The heroes 1 will fight villain 1. Both get defeated. The hero 2 fights villain 2. It wins the battle and now his health is 2. He fights the third villain and loses, the villain still has health 3. The hero 3 fights villain 3 and both get defeated. Hero 4 fights villain 4 and both get defeated. So no need to remove any villain.
        

Case#: 2

Input:
5
3
3
1
2
3
1
1

Output:
0

The fight will take place and hero 1 will defeat villain 1 and 2. Hero 2 will defeat villain 2. Hero 3 will defeat villain 3 and 4
        

Case#: 3

Input:
5
1
4
1
2
3
1
3

Output:
3

Only 1 hero is present with health 4. Since you can only remove villain from the front, you will have to remove the first 3 villains to ensure victory. The hero can fight the last 2 villain of health 1 and 3 respectively and win the battle.
        

Infosys HackWithInfy 2025

Hero Villain Battle Java Code

import java.util.*;

public class HeroVillainBattle {

    public static int findMinVillainsToRemove(int N, int M, int H, int[] villainHealth) {
        if (M >= N) return 0;
        for (int removeCount = 0; removeCount < N; removeCount++) {
            if (canHeroesWin(N - removeCount, M, H, villainHealth, removeCount)) {
                return removeCount;
            }
        }
        return N;
    }

    private static boolean canHeroesWin(int remainingVillains, int heroCount, int heroHealth, int[] villainHealth, int removeCount) {
        int[] currentVillainHealth = Arrays.copyOfRange(villainHealth, removeCount, villainHealth.length);
        List heroes = new ArrayList<>();
        for (int i = 0; i < heroCount; i++) {
            heroes.add(heroHealth);
        }
        for (int villainIndex = 0; villainIndex < currentVillainHealth.length; villainIndex++) {
            boolean heroBattled = false;
            for (int heroIndex = 0; heroIndex < heroes.size(); heroIndex++) {
                int currentHeroHealth = heroes.get(heroIndex);
                if (currentHeroHealth > currentVillainHealth[villainIndex]) {
                    heroes.set(heroIndex, currentHeroHealth - currentVillainHealth[villainIndex]);
                    heroBattled = true;
                    break;
                } else if (currentHeroHealth == currentVillainHealth[villainIndex]) {
                    heroes.remove(heroIndex);
                    heroBattled = true;
                    break;
                }
            }
            if (!heroBattled) return false;
            heroes.removeIf(h -> h <= 0);
            if (heroes.isEmpty()) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int M = scanner.nextInt();
        int H = scanner.nextInt();
        int[] villainHealth = new int[N];
        for (int i = 0; i < N; i++) {
            villainHealth[i] = scanner.nextInt();
        }
        int result = findMinVillainsToRemove(N, M, H, villainHealth);
        System.out.println(result);
        scanner.close();
    }
}
    

Python Code

def find_min_villains_to_remove(N, M, H, villain_health):
    # If heroes are more than villains, no need to remove
    if M >= N:
        return 0
    
    # Try removing different numbers of villains from the front
    for remove_count in range(N):
        if can_heroes_win(N - remove_count, M, H, villain_health[remove_count:]):
            return remove_count
    
    # If no solution found
    return N

def can_heroes_win(remaining_villains, hero_count, hero_health, villain_health):
    # Track current heroes and their health
    heroes = [hero_health] * hero_count
    
    # Simulate battles
    for villain_index, villain_health_value in enumerate(villain_health):
        # Find first available hero
        hero_battled = False
        for hero_index in range(len(heroes)):
            current_hero_health = heroes[hero_index]
            
            # Battle logic
            if current_hero_health > villain_health_value:
                # Hero wins, reduce hero health
                heroes[hero_index] -= villain_health_value
                hero_battled = True
                break
            elif current_hero_health == villain_health_value:
                # Both defeated
                heroes.pop(hero_index)
                hero_battled = True
                break
        
        # If no hero can fight, battle fails
        if not hero_battled:
            return False
        
        # Remove defeated heroes
        heroes = [h for h in heroes if h > 0]
        
        # No heroes left
        if not heroes:
            return False
    
    # All villains defeated
    return True

def main():
    # Read inputs
    N = int(input())  # Number of villains
    M = int(input())  # Number of heroes
    H = int(input())  # Hero health
    
    # Read villain health
    villain_health = [int(input()) for _ in range(N)]
    
    # Calculate and print result
    result = find_min_villains_to_remove(N, M, H, villain_health)
    print(result)

if __name__ == "__main__":
    main()
    

The solution follows the same logic as the Java version:

01. find_min_villains_to_remove() tries removing increasing numbers of villains

02. can_heroes_win() simulates battles

03. Handles battle scenarios per the original problem specification

04. Includes input processing in main()

Complexity remains O(N²*M), where N is villains and M is heroes.

JavaScript

function findMinVillainsToRemove(N, M, H, villainHealth) {
    if (M >= N) return 0;

    for (let removeCount = 0; removeCount < N; removeCount++) {
        if (canHeroesWin(N - removeCount, M, H, villainHealth.slice(removeCount))) {
            return removeCount;
        }
    }

    return N;
}

function canHeroesWin(remainingVillains, heroCount, heroHealth, villainHealth) {
    let heroes = Array(heroCount).fill(heroHealth);

    for (let villainIndex = 0; villainIndex < villainHealth.length; villainIndex++) {
        let heroBattled = false;

        for (let heroIndex = 0; heroIndex < heroes.length; heroIndex++) {
            let currentHeroHealth = heroes[heroIndex];

            if (currentHeroHealth > villainHealth[villainIndex]) {
                heroes[heroIndex] -= villainHealth[villainIndex];
                heroBattled = true;
                break;
            } else if (currentHeroHealth === villainHealth[villainIndex]) {
                heroes.splice(heroIndex, 1);
                heroBattled = true;
                break;
            }
        }

        if (!heroBattled) return false;

        heroes = heroes.filter(h => h > 0);

        if (heroes.length === 0) return false;
    }

    return true;
}

function main() {
    const testCases = [
        { N: 4, M: 4, H: 3, villainHealth: [3, 1, 3, 3] },
        { N: 5, M: 3, H: 3, villainHealth: [1, 2, 3, 1, 1] },
        { N: 5, M: 1, H: 4, villainHealth: [1, 2, 3, 1, 3] }
    ];

    testCases.forEach((testCase, index) => {
        const result = findMinVillainsToRemove(
            testCase.N, 
            testCase.M, 
            testCase.H, 
            testCase.villainHealth
        );
        console.log(`Case ${index + 1} Result: ${result}`);
    });
}

main();

CPP ( C++ )

#include <iostream>
#include <vector>
#include <algorithm>

class HeroVillainBattle {
public:
    static int findMinVillainsToRemove(int N, int M, int H, const std::vector<int>& villainHealth) {
        // If heroes are more than villains, no need to remove
        if (M >= N) return 0;
        
        // Try removing different numbers of villains from the front
        for (int removeCount = 0; removeCount < N; removeCount++) {
            std::vector<int> currentVillainHealth(
                villainHealth.begin() + removeCount, 
                villainHealth.end()
            );
            
            if (canHeroesWin(N - removeCount, M, H, currentVillainHealth)) {
                return removeCount;
            }
        }

        // If no solution found
        return N;
    }

private:
    static bool canHeroesWin(int remainingVillains, int heroCount, int heroHealth, 
                              const std::vector<int>& villainHealth) {
        // Track current heroes and their health
        std::vector<int> heroes(heroCount, heroHealth);

        // Simulate battles
        for (int villainIndex = 0; villainIndex < villainHealth.size(); villainIndex++) {
            // Find first available hero
            bool heroBattled = false;
            for (int heroIndex = 0; heroIndex < heroes.size(); heroIndex++) {
                int currentHeroHealth = heroes[heroIndex];

                // Battle logic
                if (currentHeroHealth > villainHealth[villainIndex]) {
                    // Hero wins, reduce hero health
                    heroes[heroIndex] -= villainHealth[villainIndex];
                    heroBattled = true;
                    break;
                } else if (currentHeroHealth == villainHealth[villainIndex]) {
                    // Both defeated
                    heroes.erase(heroes.begin() + heroIndex);
                    heroBattled = true;
                    break;
                }
            }

            // If no hero can fight, battle fails
            if (!heroBattled) return false;

            // Remove defeated heroes
            heroes.erase(
                std::remove_if(heroes.begin(), heroes.end(), 
                    [](int h) { return h <= 0; }
                ),
                heroes.end()
            );

            // No heroes left
            if (heroes.empty()) return false;
        }

        // All villains defeated
        return true;
    }

public:
    static void runTestCases() {
        // Test Case 1
        std::vector<int> case1 = {3, 1, 3, 3};
        std::cout << "Case 1 Result: " 
                  << findMinVillainsToRemove(4, 4, 3, case1) << std::endl;

        // Test Case 2
        std::vector<int> case2 = {1, 2, 3, 1, 1};
        std::cout << "Case 2 Result: " 
                  << findMinVillainsToRemove(5, 3, 3, case2) << std::endl;

        // Test Case 3
        std::vector<int> case3 = {1, 2, 3, 1, 3};
        std::cout << "Case 3 Result: " 
                  << findMinVillainsToRemove(5, 1, 4, case3) << std::endl;
    }
};

int main() {
    // Run predefined test cases
    HeroVillainBattle::runTestCases();
    
    // Optional: Interactive input
    int N, M, H;
    std::cin >> N >> M >> H;

    std::vector<int> villainHealth(N);
    for (int i = 0; i < N; i++) {
        std::cin >> villainHealth[i];
    }

    int result = HeroVillainBattle::findMinVillainsToRemove(N, M, H, villainHealth);
    std::cout << result << std::endl;

    return 0;
}

C

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

bool can_heroes_win(int remaining_villains, int hero_count, int hero_health, int* villain_health) {
    // Dynamically allocate heroes array
    int* heroes = malloc(hero_count * sizeof(int));

    for (int i = 0; i < hero_count; i++) {
        heroes[i] = hero_health;
    }

    int hero_count_current = hero_count;

    // Simulate battles
    for (int villain_index = 0; villain_index < remaining_villains; villain_index++) {
        bool hero_battled = false;
        
        for (int hero_index = 0; hero_index < hero_count_current; hero_index++) {
            int current_hero_health = heroes[hero_index];

            // Battle logic
            if (current_hero_health > villain_health[villain_index]) {
                // Hero wins, reduce hero health
                heroes[hero_index] -= villain_health[villain_index];
                hero_battled = true;
                break;
            } else if (current_hero_health == villain_health[villain_index]) {
                // Both defeated
                for (int j = hero_index; j < hero_count_current - 1; j++) {
                    heroes[j] = heroes[j + 1];
                }
                hero_count_current--;
                hero_battled = true;
                break;
            }
        }

        // If no hero can fight, battle fails
        if (!hero_battled) {
            free(heroes);
            return false;
        }

        // Remove defeated heroes
        for (int j = 0; j < hero_count_current; j++) {
            if (heroes[j] <= 0) {
                for (int k = j; k < hero_count_current - 1; k++) {
                    heroes[k] = heroes[k + 1];
                }
                hero_count_current--;
                j--;
            }
        }

        // No heroes left
        if (hero_count_current == 0) {
            free(heroes);
            return false;
        }
    }

    // Free memory and return
    free(heroes);
    return true;
}

int find_min_villains_to_remove(int N, int M, int H, int* villain_health) {
    // If heroes are more than villains, no need to remove
    if (M >= N) return 0;

    // Try removing different numbers of villains from the front
    for (int remove_count = 0; remove_count < N; remove_count++) {
        if (can_heroes_win(N - remove_count, M, H, villain_health + remove_count)) {
            return remove_count;
        }
    }

    // If no solution found
    return N;
}

int main() {
    int N, M, H;

    // Read inputs
    scanf("%d", &N);  // Number of villains
    scanf("%d", &M);  // Number of heroes
    scanf("%d", &H);  // Hero health

    // Allocate villain health array
    int* villain_health = malloc(N * sizeof(int));

    // Read villain health
    for (int i = 0; i < N; i++) {
        scanf("%d", &villain_health[i]);
    }

    // Calculate and print result
    int result = find_min_villains_to_remove(N, M, H, villain_health);
    printf("%d\n", result);

    // Free allocated memory
    free(villain_health);

    return 0;
}

Infosys HackWithInfy 2025

Infosys HackWithInfy 2025