Number of Burgers with No Waste of Ingredients

Medium
1134.

Number of Burgers with No Waste of Ingredients

Number of Burgers with No Waste of Ingredients is a medium coding problem on math, asked in Amazon and Google interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} tomatoSlices
 * @param {number} cheeseSlices
 * @return {number[]}
 */
var numOfBurgers = function(tomatoSlices, cheeseSlices) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

  1. Hint 1

    Write two equations: one for tomato slices and one for cheese slices.

  2. Hint 2

    With J jumbo and S small burgers: 4J + 2S = tomatoSlices and J + S = cheeseSlices.

  3. Hint 3

    Subtracting twice the second equation gives 2J = tomatoSlices - 2 * cheeseSlices; check that J and S come 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

  1. Compute d = tomatoSlices - 2 * cheeseSlices, which must equal 2J.
  2. If d is negative or odd, return [].
  3. Let J = d / 2 and S = cheeseSlices - J. If S < 0, return [].
  4. 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.
  • S can be negative even when J is 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.

All 337 math problems · the whole catalogue