Skip to content

1276. Number of Burgers with No Waste of Ingredients

SourceWeekly Contest 165 Q2DifficultyMediumRating1386

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