C++ | Begineer Friendly | Binary Search
Intuition\n Describe your first thoughts on how to solve this problem. \nTo solve the problem, the first observation is that we need to create exactly c burgers
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo solve the problem, the first observation is that we need to create exactly `c` burgers using a specified number of tomato and cheese slices. \n\nEach jumbo burger requires more tomatoes than a small burger, so we can try to determine the number of jumbo burgers we can afford to make with the given tomatoes, then use the remaining tomatoes for small burgers. \n\nThis leads to a binary search approach where we adjust the number of jumbo burgers until the sum of jumbo and small burgers equals `c`.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n1. **Check Tomato Slice Parity**: If the number of tomato slices `t` is odd, immediately return an empty result because each burger type requires an even number of tomatoes.\n2. **Binary Search for Jumbo Burgers**: Set a range for the number of jumbo burgers from `0` to the maximum possible (`t / 4`). This is because each jumbo burger consumes 4 tomato slices, so this gives the upper limit.\n3. **Calculate Small Burgers**: For each midpoint (potential number of jumbo burgers), calculate the remaining tomatoes and determine how many small burgers can be made with them.\n4. **Check Burger Count**: Sum the current jumbo and small burger counts:\n- If the sum matches `c`, return this combination as a solution.\n- If it\u2019s less than `c`, reduce the number of jumbo burgers (`right = mid`).\n- If it\u2019s more than `c`, increase the number of jumbo burgers (`left = mid + 1`).\n5. **Final Validation: After the loop**, check if the final values of `left` and `small` satisfy the required count of cheese slices. If they do, return `[left, small]`; otherwise, return an empty result.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(log(t/4))$$, where `t` is the number of tomato slices. This complexity arises from the binary search, which iterates based on the maximum possible number of jumbo burgers.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(1)$$, , since we only use a few extra variables and do not require additional data structures.\n\n# Code\n```cpp []\n#include <vector>\nusing namespace std;\n\nclass Solution {\npublic:\n    vector<int> numOfBurgers(int t, int c) {\n        if (t % 2 != 0) { // if t is odd, it\'s impossible to use up all tomatoes\n            return {};\n        }\n\n        int totalJumbo = t / 4;\n        int left = 0, right = totalJumbo;\n\n        while (left < right) {\n            int mid = (left + right) / 2;\n            int remaining = t - (4 * mid);\n            int totalSmall = remaining / 2;\n            int burgerPossible = mid + totalSmall;\n\n            if (burgerPossible == c) {\n                return {mid, totalSmall};\n            } else if (burgerPossible < c) { // we need fewer jumbos\n                right = mid;\n            } else { // we need more jumbos\n                left = mid + 1;\n            }\n        }\n\n        int remaining = t - (4 * left);\n        int small = remaining / 2;\n\n        if (left + small == c) {\n            return {left, small};\n        }\n\n        return {};\n    }\n};\n\n```
['Math', 'Binary Search', 'C++']