Tywin's War Strategy

JavaView on GFG

Problem Overview

Strategically win war by pairing soldiers optimally.

Intuition

Strategically win war by pairing soldiers optimally. Greedy matching.

Algorithm

1Sort both armies. Greedy: use weakest soldier that can beat opponent. Track wins.

Common Pitfalls

• Similar to task assignment problem. Sort and match greedily to maximize wins.

Tywin's War Strategy.java

Java

// Approach: Greedy simulation. Assign resources optimally to maximize victory count based on constraints.
// Time: O(n log n) Space: O(n)
import java.util.*;

class Solution {
    public int minSoldiers(int[] arr, int k) {
        int n = (int) Math.ceil(arr.length / 2.0);
        ArrayList<Integer> temp = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] % k != 0)
                temp.add(k - (arr[i] % k));
            else
                n = n - 1;
        }

        Collections.sort(temp);
        int res = 0;
        int count = 0;
        while (count < n) {
            res += temp.get(count);
            count++;
        }
        
        return res;
    }
}

Was this solution helpful?