Skip to content

1276. Number of Burgers with No Waste of Ingredients

Description

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

Solutions

Solution 1: Mathematics

Thinking

A jumbo takes \(4\) tomatoes and \(1\) cheese, a small takes \(2\) and \(1\), and nothing may remain. Two equations in two unknowns; we need a non-negative integer solution. Tomatoes reach \(10^7\), so enumerating one burger type is slow; the closed form is \(O(1)\).

We set the number of Jumbo Burgers as \(x\) and the number of Small Burgers as \(y\), then we have:

\[ \begin{aligned} 4x + 2y &= tomatoSlices \\ x + y &= cheeseSlices \end{aligned} \]

Transforming the above two equations, we can get:

\[ \begin{aligned} y = (4 \times cheeseSlices - tomatoSlices) / 2 \\ x = cheeseSlices - y \end{aligned} \]

Where \(x\) and \(y\) must be non-negative integers.

The time complexity is \(O(1)\), and the space complexity is \(O(1)\).

1
2
3
4
5
6
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]

1
2
3
4
5
6
7
8
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);
    }
}

1
2
3
4
5
6
7
8
9
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};
    }
};

1
2
3
4
5
6
7
8
9
func numOfBurgers(tomatoSlices int, cheeseSlices int) []int {
    k := 4*cheeseSlices - tomatoSlices
    y := k / 2
    x := cheeseSlices - y
    if k%2 != 0 || x < 0 || y < 0 {
        return []int{}
    }
    return []int{x, y}
}

1
2
3
4
5
6
function numOfBurgers(tomatoSlices: number, cheeseSlices: number): number[] {
    const k = 4 * cheeseSlices - tomatoSlices;
    const y = k >> 1;
    const x = cheeseSlices - y;
    return k % 2 || y < 0 || x < 0 ? [] : [x, y];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
impl Solution {
    pub fn num_of_burgers(tomato_slices: i32, cheese_slices: i32) -> Vec<i32> {
        let k = 4 * cheese_slices - tomato_slices;
        let y = k / 2;
        let x = cheese_slices - y;
        if k % 2 != 0 || y < 0 || x < 0 {
            Vec::new()
        } else {
            vec![x, y]
        }
    }
}

Comments