# Number of Burgers with No Waste of Ingredients
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-burgers-with-no-waste-of-ingredients)
Canonical: https://scaleengineer.com/dsa/problems/number-of-burgers-with-no-waste-of-ingredients
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
---
## Problem
Given two integers `tomatoSlices` and `cheeseSlices`. The ingredients of different burgers are as follows:

* **Jumbo Burger:** `4` tomato slices and `1` cheese slice.
* **Small Burger:** `2` Tomato slices and `1` cheese slice.

Return `[total_jumbo, total_small]` so that the number of remaining `tomatoSlices` equal to `0` and the number of remaining `cheeseSlices` equal to `0`. If it is not possible to make the remaining `tomatoSlices` and `cheeseSlices` equal to `0` return `[]`.

**Example 1:**

**Input:** tomatoSlices = 16, cheeseSlices = 7
**Output:** [1,6]
**Explantion:** To make one jumbo burger and 6 small burgers we need 4*1 + 2*6 = 16 tomato and 1 + 6 = 7 cheese.
There will be no remaining ingredients.

**Example 2:**

**Input:** tomatoSlices = 17, cheeseSlices = 4
**Output:** []
**Explantion:** There will be no way to use all ingredients to make small and jumbo burgers.

**Example 3:**

**Input:** tomatoSlices = 4, cheeseSlices = 17
**Output:** []
**Explantion:** Making 1 jumbo burger there will be 16 cheese remaining and making 2 small burgers there will be 15 cheese remaining.

**Constraints:**

* `0 <= tomatoSlices, cheeseSlices <= 107`

# Approaches
## Brute Force Iteration
This approach involves iterating through all possible combinations of jumbo and small burgers. Since the total number of burgers is fixed by the number of cheese slices (`cheeseSlices`), we can iterate through all possible numbers of one type of burger (e.g., jumbo burgers) and check if the remaining ingredients match the requirements for the other type.
**Time:** O(C), where `C` is `cheeseSlices`. The loop runs from `0` to `cheeseSlices`. Given the constraint `cheeseSlices <= 10^7`, this approach is too slow for the given constraints. · **Space:** O(1), as we only use a few variables to store the counts and the result. The space for the result list is not counted towards the auxiliary space complexity.
**Pros:** Simple to understand and implement.; Directly models the problem by trying out all possibilities.
**Cons:** Inefficient for large inputs due to its linear time complexity.; Likely to result in a 'Time Limit Exceeded' (TLE) error on coding platforms with large test cases and strict time limits.
### Explanation
The core idea is that the total number of burgers must be equal to `cheeseSlices` because each burger, regardless of type, requires exactly one slice of cheese. Let `jumbo` be the number of jumbo burgers and `small` be the number of small burgers. This gives us the equation: `jumbo + small = cheeseSlices`.

We can iterate through all possible values for `jumbo`, starting from 0 up to `cheeseSlices`. For each potential number of `jumbo` burgers, we can determine the required number of `small` burgers using `small = cheeseSlices - jumbo`. 

Then, we calculate the total number of tomato slices required for this specific combination: `required_tomatoes = 4 * jumbo + 2 * small`. If this calculated `required_tomatoes` is equal to the given `tomatoSlices`, we have found a valid combination and can return `[jumbo, small]`. If the loop completes without finding any such match, it means no solution exists, and we should return an empty list.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> numOfBurgers(int tomatoSlices, int cheeseSlices) {
        for (int jumbo = 0; jumbo <= cheeseSlices; jumbo++) {
            int small = cheeseSlices - jumbo;
            if (4 * jumbo + 2 * small == tomatoSlices) {
                List<Integer> result = new ArrayList<>();
                result.add(jumbo);
                result.add(small);
                return result;
            }
        }
        return new ArrayList<>();
    }
}
```
### Algorithm
1. Iterate with a variable `jumbo` from `0` to `cheeseSlices`.
2. In each iteration, calculate the number of small burgers: `small = cheeseSlices - jumbo`.
3. Calculate the total tomato slices needed: `tomatoes_needed = 4 * jumbo + 2 * small`.
4. Check if `tomatoes_needed` equals `tomatoSlices`.
5. If they are equal, a valid solution is found. Return `[jumbo, small]`.
6. If the loop finishes without finding a solution, return an empty list `[]`.

## Mathematical Approach using Linear Equations
This problem can be modeled as a system of two linear equations with two variables. By solving this system, we can directly calculate the required number of jumbo and small burgers without any iteration, leading to a highly efficient solution.
**Time:** O(1). The solution involves a fixed number of arithmetic operations and comparisons, regardless of the input size. This is the most optimal time complexity possible. · **Space:** O(1), as the solution only uses a few variables to perform calculations. The space for the result list is not counted towards the auxiliary space complexity.
**Pros:** Extremely efficient with constant time complexity.; Provides a direct solution without any iteration or recursion.; Handles large inputs effortlessly.
**Cons:** Requires mathematical insight to derive the formulas and conditions, which might not be immediately obvious.
### Explanation
Let `j` be the number of jumbo burgers and `s` be the number of small burgers. We can set up the following equations based on the ingredients:
1. For tomato slices: `4*j + 2*s = tomatoSlices`
2. For cheese slices: `j + s = cheeseSlices`

We can solve this system. From the second equation, we get `s = cheeseSlices - j`. Substitute this into the first equation:
`4*j + 2*(cheeseSlices - j) = tomatoSlices`
`4*j + 2*cheeseSlices - 2*j = tomatoSlices`
`2*j = tomatoSlices - 2*cheeseSlices`
`j = (tomatoSlices - 2*cheeseSlices) / 2`

Now we have a direct formula for `j`. We can then find `s` using `s = cheeseSlices - j`. For a solution to be valid, `j` and `s` must be non-negative integers. This imposes certain conditions:
- `tomatoSlices - 2*cheeseSlices` must be non-negative and even. This is because `2*j` must be a non-negative even number.
- The calculated `s` must be non-negative. `s = cheeseSlices - j >= 0`.

If these conditions are met, we can calculate `jumbo` and `small` and are guaranteed to have a valid, non-negative integer solution. Otherwise, no solution exists.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> numOfBurgers(int tomatoSlices, int cheeseSlices) {
        // Let j = jumbo burgers, s = small burgers
        // 4j + 2s = tomatoSlices
        // j + s = cheeseSlices  => s = cheeseSlices - j
        // 4j + 2(cheeseSlices - j) = tomatoSlices
        // 2j = tomatoSlices - 2*cheeseSlices
        
        int two_jumbo = tomatoSlices - 2 * cheeseSlices;

        // Check if jumbo is a non-negative integer
        if (two_jumbo < 0 || two_jumbo % 2 != 0) {
            return new ArrayList<>();
        }

        int jumbo = two_jumbo / 2;
        int small = cheeseSlices - jumbo;

        // Check if small is non-negative
        if (small < 0) {
            return new ArrayList<>();
        }

        List<Integer> result = new ArrayList<>();
        result.add(jumbo);
        result.add(small);
        return result;
    }
}
```
### Algorithm
1. Define two variables, `jumbo` and `small`, to store the number of burgers.
2. Check for impossible scenarios based on the derived mathematical conditions:
   a. The value `tomatoSlices - 2 * cheeseSlices` must be non-negative and even. If not, return `[]`.
   b. The calculated number of small burgers must be non-negative. If not, return `[]`.
3. If the checks pass, a unique solution exists. Calculate the number of jumbo burgers: `jumbo = (tomatoSlices - 2 * cheeseSlices) / 2`.
4. Calculate the number of small burgers: `small = cheeseSlices - jumbo`.
5. Return the result as a list: `[jumbo, small]`.

# Solutions
### Java

```java
class Solution { public List < Integer > numOfBurgers ( int tomatoSlices , int cheeseSlices ) { int k = 4 * cheeseSlices - tomatoSlices ; int y = k / 2 ; int x = cheeseSlices - y ; return k % 2 != 0 || y < 0 || x < 0 ? List . of () : List . of ( x , y ); } }
```

### CPP

```cpp
class Solution { public: vector < int > numOfBurgers ( int tomatoSlices , int cheeseSlices ) { int k = 4 * cheeseSlices - tomatoSlices ; int y = k / 2 ; int x = cheeseSlices - y ; return k % 2 || x < 0 || y < 0 ? vector < int > {} : vector < int > { x , y }; } };
```

### Python

```python
class Solution : def numOfBurgers ( self , tomatoSlices : int , cheeseSlices : int ) -> List [ int ]: k = 4 * cheeseSlices - tomatoSlices y = k // 2 x = cheeseSlices - y return [] if k % 2 or y < 0 or x < 0 else [ x , y ]
```