Domain 2MediumMEDIUM

Number of Burgers with No Waste of Ingredients

Solves a system of linear equations to determine burger counts, ensuring non-negative integer solutions.

Domain: medium•Updated: 2026-09-13
#algebra#mathematics#O(1)#constant space

Problem Breakdown

We are given two integers: tomatoSlices (TT) and cheeseSlices (CC). We need to construct burgers using these ingredients such that there is zero waste (all slices used exactly once). There are only two types of burgers allowed:

  1. Jumbo Burger: Consumes 4 tomato slices + 1 cheese slice.
  2. Small Burger: Consumes 2 tomato slices + 1 cheese slice.

We need to return a list [jumbo_count, small_count]. If no valid combination exists where both counts are non-negative integers and ingredients match exactly, we must return an empty list [].

Key Constraints & Edge Cases:

  • Non-negativity: The number of burgers cannot be negative. J≥0J \ge 0 and S≥0S \ge 0.
  • Integer Solution: Since burger counts are discrete items, the solution to our equations must result in integers (no fractions).
  • Zero Inputs: If both inputs are zero, we can make zero of each burger ([0, 0]).

Intuition

A naive approach might be to iterate through every possible number of Jumbo burgers from 00 to cheeseSlices, calculate the required Small burgers based on remaining cheese, and check if that satisfies the tomato constraint.

  • Brute Force Complexity: This would take O(C)O(C) time where C=cheeseSlicesC = \text{cheeseSlices}. Given constraints up to 10710^7, this risks Time Limit Exceeded (TLE) in strict environments or simply unnecessary overhead when a mathematical solution exists instantly.

Key Insight: This problem can be modeled as a system of linear equations with two variables (JJ for Jumbo, SS for Small). Since we have exact constraints on both ingredients, we don’t need to search; we just need to solve the algebraic system directly. This reduces complexity from O(C)O(C) to O(1)O(1).

Approach

We define our unknowns:

  • Let j be the number of Jumbo Burgers.
  • Let s be the number of Small Burgers.

Based on ingredient consumption, we form two equations:

  1. Cheese Constraint: Each burger uses exactly 1 cheese slice. J+S=CJ + S = C
  2. Tomato Constraint: Jumbo uses 4 tomatoes, Small uses 2 tomatoes. 4J+2S=T4J + 2S = T

Step-by-Step Derivation: From equation (1), we can express s in terms of j: S=C−JS = C - J

Substitute this into equation (2): 4J+2(C−J)=T4J + 2(C - J) = T 4J+2C−2J=T4J + 2C - 2J = T 2J+2C=T2J + 2C = T 2J=T−2C2J = T - 2C J=T−2C2J = \frac{T - 2C}{2}

Once we have j, we calculate s using S=C−JS = C - J. Finally, we must validate that both calculated values are non-negative integers. If the numerator (T−2C)(T - 2C) is negative or odd (resulting in a fraction), no valid solution exists.

Complexity Analysis

  • Time Complexity: O(1)O(1). We perform a constant number of arithmetic operations regardless of input size.
  • Space Complexity: O(1)O(1). We only store variables for the counts and intermediate calculations; we do not use auxiliary data structures that grow with input.

Solution

def numOfBurgers(tomatoSlices: int, cheeseSlices: int):
    # Calculate numerator derived from linear equation system
    # J = (T - 2C) / 2
    numerator = tomatoSlices - 2 * cheeseSlices
    
    # Check if the difference isn't divisible by 2 or results in negative count.
    # If T < 2*C, we have too few tomatoes for even all small burgers -> Invalid (numerator < 0)
    # If T is odd relative to C's contribution, integer solution impossible -> numerator % 2 != 0
    
    if numerator < 0 or numerator % 2 != 0:
        return []

    jumbo_count = numerator // 2
    small_count = cheeseSlices - jumbo_count
    
    # Ensure Small burger count is also non-negative. 
    # This handles the case where we have too many tomatoes relative to cheese (T > 4C).
    if small_count < 0:
        return []

    return [jumbo_count, small_count]

Edge Cases Handled

  • Zero Inputs: If tomatoSlices = 0 and cheeseSlices = 0, the numerator becomes 00, resulting in [0, 0]. The code handles this naturally.
  • Impossible Tomato Counts (Odd Difference): If (T - 2C) is odd, integer division would truncate incorrectly or result in a non-integer burger count. We check numerator % 2 != 0 to return [].
  • Negative Intermediate Results: If we have too many tomatoes relative to cheese (e.g., T=16,C=7T=16, C=7), the math works (J=(16−14)/2=1J = (16 - 14)/2 = 1). However if T<2CT < 2C, numerator is negative. We check numerator < 0 and return [].
  • Excess Tomatoes: If we have too many tomatoes such that even making only small burgers isn’t enough (e.g., T=8,C=1T=8, C=1), then J=(8−2)/2=3J = (8-2)/2 = 3, but S=1−3=−2S = 1 - 3 = -2. The check small_count < 0 catches this and returns [].
  • Large Inputs: Python handles large integers automatically, so overflow isn’t an issue like in fixed-width languages (Java/C++), but the logic remains constant time regardless of magnitude up to 10710^7.