Given 3 integers a, b and c indicating number of candies present in three bags. You need to find whether we can empty all the bags by performing a specific operation where in each operation, you can eat 2 candies from one bag and 1 candy each from the other 2 bags. It is not permittable to skip any bag i.e either 1 or 2 candies must be eaten from each bag in each operation. Return true if possible else return false.
Examples:
Input: 4, 2, 2
Output: true
Explanation:
Operation 1: you can eat 2 candies from bag1 and 1 from bag2 and bag3 each.
Candies left after operation 1
bag1 = 2, bag2 = 1, bag3 = 1
Operation 2: you can eat 2 candies from bag1 and 1 from each bag2 and bag3 each
Candies left after operation 2
bag1 = 0, bag2 = 0, bag3 = 0
Hence it is possible to empty all the bagsInput: 3, 4, 2
Output: false
Naive Approach: Iterate through the variables until all three does not become 0. At every iteration reduce the maximum element by 2 and remaining variables by 1.
Time Complexity: O(N), where N is value of maximum variable of a, b and c
Efficient Approach: The given problem can be solved with the efficient approach by making the following observations:
- In each operation we’ll pick 1+2+1=4 candies, hence the sum of all the candies in bag1, bag2, and bag3 must be divisible by 4.
- Number of operations required to empty all the bags would be (sum of all candies)/4.
- We have to pick either 1 or 2 candies from a bag at any operation, hence the minimum candies present of the 3 bags must be greater than or equal to the number of operations.
C++
// C++ code for the above approach#include <bits/stdc++.h>#define ll long longusing namespace std;bool can_empty(ll a, ll b, ll c){ // If total candies are not multiple // of 4 then its not possible to be // left with 0 candies if ((a + b + c) % 4 != 0) return false; else { // If minimum candies of three bags // are less than number of operations // required then the task is not possible int m = min(a, min(b, c)); if (m < ((a + b + c) / 4)) return false; } return true;}// Driver codeint main(){ ll a = 4, b = 2, c = 2; cout << (can_empty(a, b, c) ? "true" : "false") << endl; a = 3, b = 4, c = 2; cout << (can_empty(a, b, c) ? "true" : "false") << endl; return 0;} |
Java
// Java code for the above approach import java.util.*;class GFG{static boolean can_empty(int a, int b, int c){ // If total candies are not multiple // of 4 then its not possible to be // left with 0 candies if ((a + b + c) % 4 != 0) return false; else { // If minimum candies of three bags // are less than number of operations // required then the task is not possible int m = Math.min(a, Math.min(b, c)); if (m < ((a + b + c) / 4)) return false; } return true;} // Driver Codepublic static void main(String[] args){ int a = 4, b = 2, c = 2; System.out.println(can_empty(a, b, c) ? "true" : "false"); a = 3; b = 4; c = 2; System.out.println(can_empty(a, b, c) ? "true" : "false");}}// This code is contributed by code_hunt |
Python3
# Python code for the above approachdef can_empty(a, b, c): # If total candies are not multiple # of 4 then its not possible to be # left with 0 candies if ((a + b + c) % 4 != 0) : return False; else : # If minimum candies of three bags # are less than number of operations # required then the task is not possible m = min(a, min(b, c)); if (m < (a + b + c) // 4) : return False; return True;# Driver codea = 4b = 2c = 2print("true" if can_empty(a, b, c) else "false");a = 3b = 4c = 2print("true" if can_empty(a, b, c) else "false");# This code is contributed by _saurabh_jaiswal |
C#
using System;public class GFG { static bool can_empty(int a, int b, int c) { // If total candies are not multiple // of 4 then its not possible to be // left with 0 candies if ((a + b + c) % 4 != 0) return false; else { // If minimum candies of three bags // are less than number of operations // required then the task is not possible int m = Math.Min(a, Math.Min(b, c)); if (m < ((a + b + c) / 4)) return false; } return true; } // Driver Code static public void Main() { int a = 4, b = 2, c = 2; Console.WriteLine(can_empty(a, b, c) ? "true" : "false"); a = 3; b = 4; c = 2; Console.WriteLine(can_empty(a, b, c) ? "true" : "false"); }}// This code is contributed by maddler. |
Javascript
<script>// Javascript code for the above approachfunction can_empty(a, b, c) { // If total candies are not multiple // of 4 then its not possible to be // left with 0 candies if ((a + b + c) % 4 != 0) return false; else { // If minimum candies of three bags // are less than number of operations // required then the task is not possible let m = Math.min(a, Math.min(b, c)); if (m < Math.floor((a + b + c) / 4)) return false; } return true;}// Driver codelet a = 4,b = 2,c = 2;document.write(can_empty(a, b, c) ? "true" : "false");document.write("<br>");(a = 3), (b = 4), (c = 2);document.write(can_empty(a, b, c) ? "true" : "false");// This code is contributed by _saurabh_jaiswal</script> |
true false
Time Complexity: O(1) since no loop is used the algorithm takes up constant time to perform the operations
Space Complexity: O(1) since no extra array is used so the space taken by the algorithm is constant
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
