Problem

You are given a positive integer n representing an n x n cargo deck on a ship. Each cell on the deck can hold one container with a weight of exactly w.

However, the total weight of all containers, if loaded onto the deck, must not exceed the ship’s maximum weight capacity, maxWeight.

Return the maximum number of containers that can be loaded onto the ship.

Example 1

1
2
3
4
5

Input: n = 2, w = 3, maxWeight = 15
Output: 4
Explanation:
The deck has 4 cells, and each container weighs 3. The total weight of loading
all containers is 12, which does not exceed `maxWeight`.

Example 2

1
2
3
4
5

Input: n = 3, w = 5, maxWeight = 20
Output: 4
Explanation:
The deck has 9 cells, and each container weighs 5. The maximum number of
containers that can be loaded without exceeding `maxWeight` is 4.

Constraints

  • 1 <= n <= 1000
  • 1 <= w <= 1000
  • 1 <= maxWeight <= 10^9

Examples

Solution

Method 1 – Math and Greedy

Intuition

The problem is to maximize the number of containers (each of weight w) that can be loaded onto an n x n deck, without exceeding the ship’s weight limit maxWeight. The answer is simply the minimum of the total number of cells (n * n) and the maximum number of containers that fit within the weight limit (maxWeight // w).

Approach

  1. Compute the total number of cells: n * n.
  2. Compute the maximum number of containers by weight: maxWeight // w.
  3. The answer is the minimum of these two values.

Code

1
2
3
4
5
6
7
8

class Solution {
public:
    int maxContainers(int n, int w, int maxWeight) {
        int total = n * n;
        int byWeight = maxWeight / w;
        return min(total, byWeight);
    }
};
1
2
3
4
5
6
7
8

func maxContainers(n, w, maxWeight int) int {
    total := n * n
    byWeight := maxWeight / w
    if total < byWeight {
        return total
    }
    return byWeight
}
1
2
3
4
5
6
7

class Solution {
    public int maxContainers(int n, int w, int maxWeight) {
        int total = n * n;
        int byWeight = maxWeight / w;
        return Math.min(total, byWeight);
    }
}
1
2
3
4
5
6
7

class Solution {
    fun maxContainers(n: Int, w: Int, maxWeight: Int): Int {
        val total = n * n
        val byWeight = maxWeight / w
        return minOf(total, byWeight)
    }
}
1
2
3
4
5

class Solution:
    def maxContainers(self, n: int, w: int, maxWeight: int) -> int:
        total = n * n
        by_weight = maxWeight // w
        return min(total, by_weight)
1
2
3
4
5
6
7

impl Solution {
    pub fn max_containers(n: i32, w: i32, max_weight: i32) -> i32 {
        let total = n * n;
        let by_weight = max_weight / w;
        total.min(by_weight)
    }
}
1
2
3
4
5
6
7

class Solution {
    maxContainers(n: number, w: number, maxWeight: number): number {
        const total = n * n;
        const byWeight = Math.floor(maxWeight / w);
        return Math.min(total, byWeight);
    }
}

Complexity

  • ⏰ Time complexity: O(1), as only a few arithmetic operations are performed.
  • 🧺 Space complexity: O(1), as only a few variables are used.