Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1276. Number of Burgers with No Waste of Ingredients - Leetcode Solution

Code Implementation

class Solution:
    def numOfBurgers(self, tomatoSlices: int, cheeseSlices: int):
        # Let x = jumbo, y = small
        # 4x + 2y = tomatoSlices
        # x + y = cheeseSlices
        # Solve:
        # x = (tomatoSlices - 2*cheeseSlices) // 2
        # y = cheeseSlices - x
        x = tomatoSlices - 2 * cheeseSlices
        if x < 0 or x % 2 != 0:
            return []
        x //= 2
        y = cheeseSlices - x
        if y < 0:
            return []
        return [x, y]
      
class Solution {
public:
    vector<int> numOfBurgers(int tomatoSlices, int cheeseSlices) {
        // Let x = jumbo, y = small
        // 4x + 2y = tomatoSlices
        // x + y = cheeseSlices
        // x = (tomatoSlices - 2*cheeseSlices)/2
        int x = tomatoSlices - 2 * cheeseSlices;
        if (x < 0 || x % 2 != 0) return {};
        x /= 2;
        int y = cheeseSlices - x;
        if (y < 0) return {};
        return {x, y};
    }
};
      
class Solution {
    public List<Integer> numOfBurgers(int tomatoSlices, int cheeseSlices) {
        // Let x = jumbo, y = small
        // 4x + 2y = tomatoSlices
        // x + y = cheeseSlices
        int x = tomatoSlices - 2 * cheeseSlices;
        if (x < 0 || x % 2 != 0) return new ArrayList<>();
        x /= 2;
        int y = cheeseSlices - x;
        if (y < 0) return new ArrayList<>();
        return Arrays.asList(x, y);
    }
}
      
var numOfBurgers = function(tomatoSlices, cheeseSlices) {
    // Let x = jumbo, y = small
    // 4x + 2y = tomatoSlices
    // x + y = cheeseSlices
    let x = tomatoSlices - 2 * cheeseSlices;
    if (x < 0 || x % 2 !== 0) return [];
    x = Math.floor(x / 2);
    let y = cheeseSlices - x;
    if (y < 0) return [];
    return [x, y];
};

Problem Description

You are given two integers: tomatoSlices and cheeseSlices. There are only two types of burgers you can make:
  • Jumbo Burger: requires 4 tomato slices and 1 cheese slice
  • Small Burger: requires 2 tomato slices and 1 cheese slice
Your task is to find out how many Jumbo and Small burgers you can make using exactly all the provided tomato and cheese slices, with no leftovers.

Return a list containing the number of Jumbo and Small burgers you can make in that order. If there is no possible solution, return an empty list. Each ingredient must be used exactly once and you cannot reuse or split any slice.

Thought Process

To solve this problem, you need to figure out if there is a way to use up all the tomato and cheese slices with the two types of burgers.

At first, you might think about trying all combinations (brute-force), but that would be inefficient for large numbers.

Instead, realize that you have two equations:
  • Each Jumbo burger uses 4 tomatoes and 1 cheese
  • Each Small burger uses 2 tomatoes and 1 cheese
Let x be the number of Jumbo burgers and y the number of Small burgers. Then:
  • 4x + 2y = tomatoSlices
  • x + y = cheeseSlices
The goal is to solve these equations for non-negative integer solutions.

Solution Approach

To solve the system of equations:
  1. Express one variable in terms of the other: From x + y = cheeseSlices, y = cheeseSlices - x.
  2. Substitute into the first equation:
    • 4x + 2y = tomatoSlices
    • Replace y: 4x + 2(cheeseSlices - x) = tomatoSlices
    • Simplify: 4x + 2cheeseSlices - 2x = tomatoSlices
    • 2x = tomatoSlices - 2cheeseSlices
    • x = (tomatoSlices - 2 * cheeseSlices) / 2
  3. Calculate y: y = cheeseSlices - x
  4. Check for validity:
    • x and y must be integers, so tomatoSlices - 2 * cheeseSlices must be even.
    • x and y must be non-negative.
  5. Return the result: If all checks pass, return [x, y], otherwise return an empty list.
This approach is efficient and avoids unnecessary computation.

Example Walkthrough

Let's take tomatoSlices = 16 and cheeseSlices = 7 as an example.
  1. Calculate x = (16 - 2*7)/2 = (16 - 14)/2 = 1
  2. Calculate y = 7 - 1 = 6
  3. Check:
    • Are both x and y non-negative? Yes.
    • Do they satisfy the original equations?
      • 4*1 + 2*6 = 4 + 12 = 16 (matches tomatoSlices)
      • 1 + 6 = 7 (matches cheeseSlices)
  4. Therefore, the answer is [1, 6]: 1 Jumbo and 6 Small burgers.

Time and Space Complexity

Brute-force Approach:
  • You might try all possible values for Jumbo and Small burgers. The number of possibilities is up to cheeseSlices, so time complexity is O(N), where N is cheeseSlices.
  • Space complexity is O(1) since you only track the current combination.
Optimized Approach (as above):
  • You compute the answer directly with a few arithmetic operations, so time complexity is O(1).
  • Space complexity is also O(1), as you only use a few variables.

Summary

This problem can be elegantly solved by setting up and solving two simple equations for two variables. By expressing one variable in terms of the other and substituting, you can directly compute the number of each type of burger. This avoids brute-force and makes the solution both efficient and easy to understand. The key insight is recognizing the problem structure and translating it to equations, then carefully checking for integer and non-negative solutions.