Given an array arr[] of size 3 denoting the number of balls of type 1, 2, and 3 respectively, the task is to find the maximum number of moves that can be performed if in one move, three balls, out of which at least 2 balls of different types, are removed.
Examples:
Input: arr[] = {2, 3, 3}
Output: 2
Explanation:
Move 1: Remove 1 ball of each type. Therefore, arr[] becomes {1, 2, 2}.
Move 2: Remove 1 ball of each type. Therefore, arr[] becomes {0, 1, 1}.
No further moves can be performed.Input: arr[] = {100, 1, 2}
Output: 3
Explanation:
Move 1: Remove 1 ball of type 2 and 2 balls of type 1. Therefore, arr[] becomes {98, 0, 2}.
Move 2: Remove 1 ball of type 3 and 2 balls of type 1. Therefore, arr[] becomes {96, 0, 1}.
Move 3: Remove 1 ball of type 3 and 2 balls of type 1. Therefore, arr[] becomes {94, 0, 0}.
No further moves can be performed.
Approach: The idea to sort the array in increasing order and then arises two cases:
- If arr[2] is smaller than 2 * (arr[0] + arr[1]), the answer will be (arr[0] + arr[1] + arr[2]) / 3.
- If arr[2] is greater than 2 * (arr[0] + arr[1]), the answer will be arr[0] + arr[1].
Follow the steps below to solve the problem:
- Sort the array in increasing order.
- Print the minimum of (arr[0]+arr[1]+arr[2])/3 and arr[0]+arr[1].
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find maximum moves that// can be performed if in each move 3// balls of different types are removedvoid findMoves(int arr[]){ // Sort the array in increasing order sort(arr, arr + 3); // Print the answer cout << (min(arr[0] + arr[1], (arr[0] + arr[1] + arr[2]) / 3));}// Driver Codeint main(){ // Given Input int arr[3] = { 2, 3, 3 }; // Function Call findMoves(arr); return 0;} |
Java
// Java program for the above approachimport java.util.Arrays; class GFG{ // Function to find maximum moves that// can be performed if in each move 3// balls of different types are removedstatic void findMoves(int arr[]){ // Sort the array in increasing order Arrays.sort(arr); // Print the answer System.out.println(Math.min(arr[0] + arr[1], (arr[0] + arr[1] + arr[2]) / 3));}// Driver Codepublic static void main(String[] args) { // Given Input int arr[] = { 2, 3, 3 }; // Function Call findMoves(arr);}}// This code is contributed by AnkThon |
Python3
# Python3 program for the above approach# Function to find maximum moves that# can be performed if in each move 3# balls of different types are removeddef findMoves(arr): # Sort the array in increasing order arr = sorted(arr) # Print the answer print (min(arr[0] + arr[1], (arr[0] + arr[1] + arr[2]) // 3))# Driver Codeif __name__ == '__main__': # Given Input arr = [ 2, 3, 3 ] # Function Call findMoves(arr)# This code is contributed by mohit kumar 29 |
C#
// Java program for the above approachusing System; class GFG{ // Function to find maximum moves that// can be performed if in each move 3// balls of different types are removedstatic void findMoves(int []arr){ // Sort the array in increasing order Array.Sort(arr); // Print the answer Console.Write(Math.Min(arr[0] + arr[1], (arr[0] + arr[1] + arr[2]) / 3));}// Driver Codepublic static void Main(String[] args) { // Given Input int []arr = { 2, 3, 3 }; // Function Call findMoves(arr);}}// This code is contributed by shivanisinghss2110 |
Javascript
<script>// JavaScript program for the above approach // Function to find maximum moves that // can be performed if in each move 3 // balls of different types are removed function findMoves(arr) { // Sort the array in increasing order arr.sort(function (a, b) { return a - b; }) // Print the answer document.write(Math.min(arr[0] + arr[1], parseInt((arr[0] + arr[1] + arr[2]) / 3))); } // Driver Code // Given Input let arr = [2, 3, 3]; // Function Call findMoves(arr); // This code is contributed by Potta Lokesh </script> |
2
Time Complexity: O(1)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!