Maximizar las extracciones de bolas de al menos dos tipos diferentes

Dada una array arr[] de tamaño 3 que indica el número de bolas de tipo 1, 2 y 3 respectivamente, la tarea es encontrar el número máximo de movimientos que se pueden realizar si en un movimiento, tres bolas, de las cuales en se eliminan al menos 2 bolas de diferentes tipos.

Ejemplos:

Entrada: arr[] = {2, 3, 3}
Salida: 2
Explicación:
Movimiento 1: Retire 1 bola de cada tipo. Por lo tanto, arr[] se convierte en {1, 2, 2}.
Movimiento 2: Retire 1 bola de cada tipo. Por lo tanto, arr[] se convierte en {0, 1, 1}.
No se pueden realizar más movimientos.

Entrada: arr[] = {100, 1, 2}
Salida: 3
Explicación:
Movimiento 1: Retire 1 bola de tipo 2 y 2 bolas de tipo 1. Por lo tanto, arr[] se convierte en {98, 0, 2}.
Movimiento 2: Elimina 1 bola de tipo 3 y 2 bolas de tipo 1. Por lo tanto, arr[] se convierte en {96, 0, 1}.
Movimiento 3: Elimina 1 bola de tipo 3 y 2 bolas de tipo 1. Por lo tanto, arr[] se convierte en {94, 0, 0}.
No se pueden realizar más movimientos.

Planteamiento: La idea de ordenar la array en orden creciente y luego surge dos casos:

• Si arr[2] es menor que 2 * (arr[0] + arr[1]) , la respuesta será (arr[0] + arr[1] + arr[2]) / 3 .
• Si arr[2] es mayor que 2 * (arr[0] + arr[1]) , la respuesta será arr[0] + arr[1] .

Siga los pasos a continuación para resolver el problema:

• Ordena la array en orden creciente .
• Imprime el mínimo de (arr[0]+arr[1]+arr[2])/3 y arr[0]+arr[1] .

A continuación se muestra la implementación del enfoque anterior:

// 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 removed
void 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 Code
int main()
{
    // Given Input
    int arr[3] = { 2, 3, 3 };
 
    // Function Call
    findMoves(arr);
 
    return 0;
}

// Java program for the above approach
import java.util.Arrays;  
 
class GFG{
     
// Function to find maximum moves that
// can be performed if in each move 3
// balls of different types are removed
static 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 Code
public static void main(String[] args)
{
     
    // Given Input
    int arr[] = { 2, 3, 3 };
 
    // Function Call
    findMoves(arr);
}
}
 
// This code is contributed by AnkThon

# 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 removed
def 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 Code
if __name__ == '__main__':
     
    # Given Input
    arr = [ 2, 3, 3 ]
 
    # Function Call
    findMoves(arr)
 
# This code is contributed by mohit kumar 29

// Java program for the above approach
using System;  
class GFG
{
     
// Function to find maximum moves that
// can be performed if in each move 3
// balls of different types are removed
static 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 Code
public static void Main(String[] args)
{
     
    // Given Input
    int []arr = { 2, 3, 3 };
 
    // Function Call
    findMoves(arr);
}
}
 
// This code is contributed by shivanisinghss2110

<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

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)