Burgers At Ninja-Cafe

Easy

0/40

Average time to solve is 15m

1 upvote

Asked in company

Problem statement

You are a chef at NINJA-CAFE. There are 2 types of burgers made there. 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.

You are given two integers 'TOMATO_SLICES' and 'CHEESE_SLICES' indicating the number of tomato slices and cheese slices available.

Your task is to return an array/list [JUMBO_BURGERS, SMALL_BURGERS] indicating the number of Jumbo Burgers and Small Burgers you can make such that the number of remaining 'TOMATO_SLICES' and the number of remaining 'CHEESE_SLICES' each equals to 0. If it is not possible to make the remaining 'TOMATO_SLICES' and 'CHEESE_SLICES' equal to 0 return [-1, -1].

For Example :

Given:-
‘TOMATO_SLICES’ = 6 and ‘CHEESE_SLICES’ = 2.
Therefore 1 Jumbo Burger and 1 Small Burger can be formed using the available slice completely.
Hence the answer is  [1, 1].

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line of input contains an integer T denoting the number of test cases.

The next ‘T’ lines contain exactly 2 space-separated integers, ‘TOMATO_SLICES’ and ‘CHEESE_SLICES’, which represent the number of tomato slices and cheese slices available respectively.

Output Format :

For each test case, print an integer denoting the total number of burgers of each type that can be formed.

The output of each test case will be printed in a separate line.

Note :

You don't have to print anything, it has already been taken care of. Just implement the given function.

If the number of ‘CHEESE_SLICES’ or ‘TOMATO_SLICES’ can’t be made 0, then return [-1, -1]

Constraints :

1 <= T <= 10
0 <= CHEESE_SLICES,TOMATO_SLICES <= 10 ^ 8

Time limit: 1 sec

Sample Input 1 :

2
6 2
7 2

Sample Output 1 :

1 1
-1 -1

Explanation of Sample Input 1 :

For first test case :  
‘TOMATO_SLICES’ = 6 and ‘CHEESE_SLICES’ = 2. Therefore 1 Jumbo Burger and 1 Small Burger can be made.
Hence the answer is  [1, 1].

For Second Test case:
TOMATO_SLICES’ = 7 and ‘CHEESE_SLICES’ = 2. Therefore 1 Jumbo Burger and 1 Small Burger can be formed but even after than 1 ‘TOMATO_SLICE’ will remain unused.
Hence the answer is [-1, -1].

Sample Input 2 :

2
16 7
0 0

Sample Output 2 :

1 6
0 0

Hint 1

Hint 2

Can we brute force?

Approaches (2)

Approach 1

Approach 2

Brute Force

The main idea is to loop from 1 to the number of ‘CHEESE_SLICES’ we have and for each, calculate if, for the given number of ‘CHEESE_SLICES’, if we can make ‘SMALL_BURGERS’, can we use the rest of the ‘TOMOATO_SLICES’ in the ‘JUMBO_BURGERS’.

Maintain an array ‘RES’ initialized to {-1, -1}.
Loop ‘SMALL_BURGER’ from 1 to ‘CHEESE_SLICES’.
- For the current ‘SMALL_BURGER’, ‘JUMBO_BURGER’ = ‘CHEESE_SLICES’ - ‘SMALL_BURGER’.
- If 2 * ’SMALL_BURGER’ + 4* ’JUMBO_BURGER’ equals the given ‘TOMATO_SLICES’, then we found our answer. Return {’ JUMBO_BURGER’, ’SMALL_BURGER’}.
Return ‘RES’ as a result.

Time Complexity

O(N), where N is the number of ‘CHEES_ESLICES’.

Since we are looping from 1 to ‘N’ that is the number of ‘CHEESE_SLICES’ therefore net complexity is O(N).

Space Complexity

O(1).

Since we are not using any extra space.

(100% EXP penalty)

Burgers At Ninja-Cafe

Console