1import java.util.List;
2
3class Solution {
4    private List<Integer> strength; // A list holding the strength values of each element.
5    private Integer[] memoizationArray; // Memoization array for storing already computed results.
6    private int numberOfK; // The 'k' parameter provided to balance with 'strength'.
7    private int totalElements; // Total number of elements in the 'strength' list.
8
9    public int findMinimumTime(List<Integer> strength, int K) {
10        // Initialize the number of elements in the list.
11        totalElements = strength.size();
12      
13        // Initialize the memoization array with null values, can store up to 2^n values
14        memoizationArray = new Integer[1 << totalElements];
15      
16        // Store the 'k' value for further calculations
17        numberOfK = K;
18      
19        // Associate the incoming 'strength' list to the instance variable
20        this.strength = strength;
21      
22        // Start the DFS from an initial state represented by '0' (no elements considered)
23        return calculateTime(0);
24    }
25
26    // Depth First Search helper method that works through subsets of elements using bit masking
27    private int calculateTime(int subsetMask) {
28        // Base case: if all elements are considered, return 0 time
29        if (subsetMask == (1 << totalElements) - 1) {
30            return 0;
31        }
32
33        // If already calculated, return the result from the memoization array
34        if (memoizationArray[subsetMask] != null) {
35            return memoizationArray[subsetMask];
36        }
37
38        // Count elements currently in the subset (determined by 'subsetMask')
39        int countElementsInSubset = Integer.bitCount(subsetMask);
40      
41        // Calculate the starting time factor based on the count of chosen elements
42        int timeFactor = 1 + countElementsInSubset * numberOfK;
43
44        // Initialize the minimum time to a large value
45        memoizationArray[subsetMask] = Integer.MAX_VALUE;
46      
47        // Try to include each element in the subset that is currently not included
48        for (int j = 0; j < totalElements; ++j) {
49            // Check if the element 'j' is not in the subset
50            if ((subsetMask >> j & 1) == 0) {
51                // Calculate the minimum time for this new subset configuration
52                memoizationArray[subsetMask] = Math.min(
53                    memoizationArray[subsetMask],
54                    calculateTime(subsetMask | (1 << j)) + (strength.get(j) + timeFactor - 1) / timeFactor
55                );
56            }
57        }
58
59        // Return the calculated minimum time for this subset configuration
60        return memoizationArray[subsetMask];
61    }
62}
63

1#include <vector>
2#include <cstring>
3#include <climits>
4
5class Solution {
6public:
7    int findMinimumTime(std::vector<int>& strength, int K) {
8        int n = strength.size(); // Number of soldiers
9        int dp[1 << n]; // DP array to store the minimum time for each state
10        std::memset(dp, -1, sizeof(dp)); // Initialize the DP array with -1 to indicate unvisited states
11
12        auto dfs = [&](auto&& self, int state) -> int {
13            if (state == (1 << n) - 1) { // All soldiers have been processed
14                return 0;
15            }
16            if (dp[state] != -1) { // If the state has already been computed, retrieve it
17                return dp[state];
18            }
19          
20            int enabledSoldiersCount = __builtin_popcount(state); // Count the number of enabled soldiers
21            int strengthFactor = 1 + K * enabledSoldiersCount; // Calculate the increase factor based on enabled soldiers
22          
23            dp[state] = INT_MAX; // Initialize the current state as maximum for comparison purposes
24          
25            for (int j = 0; j < n; ++j) {
26                // If soldier j is not yet enabled in this state
27                if ((state >> j & 1) == 0) {
28                    // Update the dp value by selecting soldier j and adding the necessary time
29                    dp[state] = std::min(dp[state], 
30                                         self(self, state | (1 << j)) + 
31                                         (strength[j] + strengthFactor - 1) / strengthFactor);
32                }
33            }
34            return dp[state];
35        };
36      
37        return dfs(dfs, 0); // Start DFS with state 0, no soldiers processed
38    }
39};
40

1// Calculate the minimum effort required to defeat all enemies
2function findMinimumTime(strength: number[], K: number): number {
3    const n = strength.length;  // Get the number of enemies
4    const f: number[] = Array(1 << n).fill(-1);  // Initialize memoization array with -1
5
6    // Depth-first search to explore all subsets of enemies
7    const dfs = (i: number): number => {
8        if (i === (1 << n) - 1) {
9            return 0;  // Base case: all enemies are defeated
10        }
11        if (f[i] !== -1) {
12            return f[i];  // Retrieve cached result if available
13        }
14        f[i] = Infinity;  // Set initial value for comparison
15
16        const x = 1 + K * bitCount(i);  // Compute effort multiplier based on defeated enemies count
17        for (let j = 0; j < n; ++j) {
18            if (((i >> j) & 1) === 0) {  // Check if the j-th enemy is undefeated
19                // Update the minimum effort required using recursive DFS
20                f[i] = Math.min(f[i], dfs(i | (1 << j)) + Math.ceil(strength[j] / x));
21            }
22        }
23        return f[i];  // Return the computed minimum effort
24    };
25
26    return dfs(0);  // Start DFS with no enemies defeated initially
27}
28
29// Count the number of set bits (1s) in the binary representation of a number
30function bitCount(i: number): number {
31    i = i - ((i >>> 1) & 0x55555555);  // Pairwise bit add
32    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);  // Sum pairs
33    i = (i + (i >>> 4)) & 0x0f0f0f0f;  // Sum nibbles
34    i = i + (i >>> 8);  // Sum bytes
35    i = i + (i >>> 16); // Sum 16-bit chunks
36    return i & 0x3f;  // Mask to keep only lower 6 bits which represents the count
37}
38