Maximum Bags With Full Capacity of Rocks

Problem Statement

In this tutorial, we will solve the Maximum Bags With Full Capacity of Rocks problem . We will provide the implementation of the solution in Python, Java, and C++.

Problem Description

You have n bags numbered from 0 to n - 1. You are given two 0-indexed integer arrays capacity and rocks. The ith bag can hold a maximum of capacity[i] rocks and currently contains rocks[i] rocks. You are also given an integer additionalRocks, the number of additional rocks you can place in any of the bags.

Return the maximum number of bags that could have full capacity after placing the additional rocks in some bags.

Examples

Example 1: Input: capacity = [2,3,4,5], rocks = [1,2,4,4], additionalRocks = 2 Output: 3 Explanation: Place 1 rock in bag 0 and 1 rock in bag 1. The number of rocks in each bag are now [2,3,4,4]. Bags 0, 1, and 2 have full capacity. There are 3 bags at full capacity, so we return 3. It can be shown that it is not possible to have more than 3 bags at full capacity. Note that there may be other ways of placing the rocks that result in an answer of 3. Example 2: Input: capacity = [10,2,2], rocks = [2,2,0], additionalRocks = 100 Output: 3 Explanation: Place 8 rocks in bag 0 and 2 rocks in bag 2. The number of rocks in each bag are now [10,2,2]. Bags 0, 1, and 2 have full capacity. There are 3 bags at full capacity, so we return 3. It can be shown that it is not possible to have more than 3 bags at full capacity. Note that we did not use all of the additional rocks.

Constraints

• n == capacity.length == rocks.length
• 1 <= n <= 5 * 104
• 1 <= capacity[i] <= 109
• 0 <= rocks[i] <= capacity[i]
• 1 <= additionalRocks <= 109

Solution of Given Problem

Intuition and Approach

The problem can be solved using a brute force approach or an optimized Technique.

• Brute Force
• Optimized approach

Approach 1:Brute Force (Naive)

Brute Force Approach: The brute force approach involves trying every possible way to distribute the additional rocks among the bags to maximize the number of full bags. This approach is infeasible for large inputs due to its high complexity.

Codes in Different Languages

C++

Written by @AmruthaPariprolu

#include <vector>
#include <algorithm>

int distributeRocks(std::vector<int>& capacity, std::vector<int>& rocks, int additionalRocks, int idx) {
    if (idx == capacity.size() || additionalRocks == 0) {
        int fullBags = 0;
        for (int i = 0; i < capacity.size(); ++i) {
            if (rocks[i] == capacity[i]) {
                ++fullBags;
            }
        }
        return fullBags;
    }

    int maxBags = distributeRocks(capacity, rocks, additionalRocks, idx + 1);

    for (int i = 1; i <= additionalRocks; ++i) {
        if (rocks[idx] + i <= capacity[idx]) {
            rocks[idx] += i;
            maxBags = std::max(maxBags, distributeRocks(capacity, rocks, additionalRocks - i, idx + 1));
            rocks[idx] -= i;
        }
    }

    return maxBags;
}

int maximumBagsBruteForce(std::vector<int>& capacity, std::vector<int>& rocks, int additionalRocks) {
    return distributeRocks(capacity, rocks, additionalRocks, 0);
}

Java

Written by @AmruthaPariprolu

import java.util.*;

public class BruteForceSolution {
    public int distributeRocks(int[] capacity, int[] rocks, int additionalRocks, int idx) {
        if (idx == capacity.length || additionalRocks == 0) {
            int fullBags = 0;
            for (int i = 0; i < capacity.length; ++i) {
                if (rocks[i] == capacity[i]) {
                    ++fullBags;
                }
            }
            return fullBags;
        }

        int maxBags = distributeRocks(capacity, rocks, additionalRocks, idx + 1);

        for (int i = 1; i <= additionalRocks; ++i) {
            if (rocks[idx] + i <= capacity[idx]) {
                rocks[idx] += i;
                maxBags = Math.max(maxBags, distributeRocks(capacity, rocks, additionalRocks - i, idx + 1));
                rocks[idx] -= i;
            }
        }

        return maxBags;
    }

    public int maximumBagsBruteForce(int[] capacity, int[] rocks, int additionalRocks) {
        return distributeRocks(capacity, rocks, additionalRocks, 0);
    }
}
 

Python

Written by @AmruthaPariprolu

def distribute_rocks(capacity, rocks, additional_rocks, idx):
    if idx == len(capacity) or additional_rocks == 0:
        full_bags = sum(1 for i in range(len(capacity)) if rocks[i] == capacity[i])
        return full_bags
    
    max_bags = distribute_rocks(capacity, rocks, additional_rocks, idx + 1)

    for i in range(1, additional_rocks + 1):
        if rocks[idx] + i <= capacity[idx]:
            rocks[idx] += i
            max_bags = max(max_bags, distribute_rocks(capacity, rocks, additional_rocks - i, idx + 1))
            rocks[idx] -= i

    return max_bags

def maximum_bags_brute_force(capacity, rocks, additional_rocks):
    return distribute_rocks(capacity, rocks, additional_rocks, 0)

Complexity Analysis

• Time Complexity: $O(2^n)$
• due to trying all combinations.
• Space Complexity: $O(n)$
• for the recursive stack.

---

Authors:

Loading...