Number of Burgers with No Waste of Ingredients — Solution
Number of Burgers with No Waste of Ingredients solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Number of Burgers with No Waste of Ingredients is a medium coding problem on math, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Math
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
The CodeKairo canteen makes two kinds of burger:
- a Jumbo Burger uses 4 tomato slices and 1 cheese slice;
- a Small Burger uses 2 tomato slices and 1 cheese slice.
Given tomatoSlices and cheeseSlices, find how many of each burger to make so that no slice of either ingredient is left over. Return [total_jumbo, total_small].
If it is impossible to use up both ingredients exactly, return an empty array []. (When a solution exists it is unique.)
Example 1
Input: tomatoSlices = 20, cheeseSlices = 6
Output: [4,2]
Explanation: 4 Jumbo use 16 tomato + 4 cheese, 2 Small use 4 tomato + 2 cheese.
Example 2
Input: tomatoSlices = 17, cheeseSlices = 4
Output: []
Explanation: Every burger uses an even number of tomato slices.
Example 3
Input: tomatoSlices = 0, cheeseSlices = 0
Output: [0,0]
Constraints
0 <= tomatoSlices, cheeseSlices <= 10^7
Hints for Number of Burgers with No Waste of Ingredients
Hint 1
Write two equations: one for tomato slices and one for cheese slices.
Hint 2
With
Jjumbo andSsmall burgers:4J + 2S = tomatoSlicesandJ + S = cheeseSlices.Hint 3
Subtracting twice the second equation gives
2J = tomatoSlices - 2 * cheeseSlices; check thatJandScome out as non-negative integers.
How to solve Number of Burgers with No Waste of Ingredients
Two unknowns, two linear equations: solve them directly and check the answer is a pair of non-negative integers.
Approach
- Compute
d = tomatoSlices - 2 * cheeseSlices, which must equal2J. - If
dis negative or odd, return[]. - Let
J = d / 2andS = cheeseSlices - J. IfS < 0, return[]. - Otherwise return
[J, S].
Why it works
The system 4J + 2S = T, J + S = C has the unique solution J = (T - 2C) / 2, S = C - J. Burgers come in whole, non-negative quantities, so the ingredients can be used exactly if and only if both values are non-negative integers.
Complexity
- Time —
O(1) - Space —
O(1)
Pitfalls
- An odd tomato count can never work — check parity before dividing.
Scan be negative even whenJis fine (too many tomatoes for the cheese).- Return an empty array, not
[0, 0], when there is no solution;[0,0]is the correct answer only for zero ingredients.
Reference solution
Python
from typing import List
def numOfBurgers(tomatoSlices: int, cheeseSlices: int) -> List[int]:
d = tomatoSlices - 2 * cheeseSlices
if d < 0 or d % 2 != 0:
return []
jumbo = d // 2
small = cheeseSlices - jumbo
if small < 0:
return []
return [jumbo, small]Java
public static int[] numOfBurgers(int tomatoSlices, int cheeseSlices) {
int d = tomatoSlices - 2 * cheeseSlices;
if (d < 0 || d % 2 != 0) return new int[0];
int jumbo = d / 2;
int small = cheeseSlices - jumbo;
if (small < 0) return new int[0];
return new int[] { jumbo, small };
}C++
vector<int> numOfBurgers(int tomatoSlices, int cheeseSlices) {
int d = tomatoSlices - 2 * cheeseSlices;
if (d < 0 || d % 2 != 0) return {};
int jumbo = d / 2;
int small = cheeseSlices - jumbo;
if (small < 0) return {};
return { jumbo, small };
}JavaScript
var numOfBurgers = function(tomatoSlices, cheeseSlices) {
var d = tomatoSlices - 2 * cheeseSlices;
if (d < 0 || d % 2 !== 0) return [];
var jumbo = d / 2;
var small = cheeseSlices - jumbo;
if (small < 0) return [];
return [jumbo, small];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.