Partidos mínimos que el equipo necesita ganar para clasificarse

Dados dos números enteros X e Y , donde X indica el número de puntos necesarios para clasificar e Y indica el número de partidos restantes . El equipo recibe 2 puntos por ganar el partido y 1 punto por perder . La tarea es encontrar el número mínimo de partidos que el equipo necesita ganar para clasificarse para la siguiente ronda.
Ejemplos: 
 

Entrada: X = 10, Y = 5 
Salida: 5 
El equipo necesita ganar todos los partidos para obtener 10 puntos.
Entrada: X = 6, Y = 5 
Salida: 1 
Si el equipo gana un solo partido y pierde los 4 partidos restantes, igual se clasificaría. 
 

Un enfoque ingenuo es verificar iterando todos los valores de 0 a Y y encontrar el primer valor que nos da X puntos. 
Un enfoque eficiente es realizar una búsqueda binaria en el número de partidos que se ganarán para averiguar el número mínimo de partidos. Inicialmente low = 0 y high = X , y luego verificamos la condición (mid * 2 + (y – mid)) ≥ x . Si la condición prevalece, verifique si existe algún valor más bajo en la mitad izquierda, es decir , alto = medio – 1; de lo contrario, verifique en la mitad derecha, es decir, bajo = medio + 1 . 
A continuación se muestra la implementación del enfoque anterior:
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the minimum number of
// matches to win to qualify for next round
int findMinimum(int x, int y)
{
 
    // Do a binary search to find
    int low = 0, high = y;
    while (low <= high) {
 
        // Find mid element
        int mid = (low + high) >> 1;
 
        // Check for condition
        // to qualify for next round
        if ((mid * 2 + (y - mid)) >= x)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return low;
}
 
// Driver Code
int main()
{
    int x = 6, y = 5;
    cout << findMinimum(x, y);
 
    return 0;
}

// Java implementation of the approach
import java.io.*;
 
class GFG
{
     
// Function to return the minimum number of
// matches to win to qualify for next round
static int findMinimum(int x, int y)
{
 
    // Do a binary search to find
    int low = 0, high = y;
    while (low <= high)
    {
 
        // Find mid element
        int mid = (low + high) >> 1;
 
        // Check for condition
        // to qualify for next round
        if ((mid * 2 + (y - mid)) >= x)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return low;
}
 
// Driver Code
public static void main (String[] args)
{
    int x = 6, y = 5;
    System.out.println(findMinimum(x, y));
}
}
 
// This code is contributed by ajit.

# Python 3 implementation of the approach
 
# Function to return the minimum number of
# matches to win to qualify for next round
def findMinimum(x, y):
     
    # Do a binary search to find
    low = 0
    high = y
    while (low <= high):
         
        # Find mid element
        mid = (low + high) >> 1
 
        # Check for condition
        # to qualify for next round
        if ((mid * 2 + (y - mid)) >= x):
            high = mid - 1
        else:
            low = mid + 1
    return low
 
# Driver Code
if __name__ == '__main__':
    x = 6
    y = 5
    print(findMinimum(x, y))
     
# This code is contributed by
# Surendra_Gangwar

// C# implementation of the approach
using System;
 
class GFG
{
         
// Function to return the minimum number of
// matches to win to qualify for next round
static int findMinimum(int x, int y)
{
 
    // Do a binary search to find
    int low = 0, high = y;
    while (low <= high)
    {
 
        // Find mid element
        int mid = (low + high) >> 1;
 
        // Check for condition
        // to qualify for next round
        if ((mid * 2 + (y - mid)) >= x)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return low;
}
 
// Driver code
static public void Main()
{
    int x = 6, y = 5;
    Console.WriteLine(findMinimum(x, y));
}
}
 
// This Code is contributed by ajit.

<?php
// PHP implementation of the approach
 
// Function to return the minimum number of
// matches to win to qualify for next round
function findMinimum($x, $y)
{
 
    // Do a binary search to find
    $low = 0; $high = $y;
    while ($low <= $high)
    {
 
        // Find mid element
        $mid = ($low + $high) >> 1;
 
        // Check for condition$
        // to qualify for next round
        if (($mid * 2 + ($y - $mid)) >= $x)
            $high = $mid - 1;
        else
            $low = $mid + 1;
    }
    return $low;
}
 
// Driver Code
$x = 6; $y = 5;
echo findMinimum($x, $y);
 
// This code has been contributed
// by 29AjayKumar
?>

<script>
    // Javascript implementation of the approach
     
    // Function to return the minimum number of
    // matches to win to qualify for next round
    function findMinimum(x, y)
    {
 
        // Do a binary search to find
        let low = 0, high = y;
        while (low <= high) {
 
            // Find mid element
            let mid = (low + high) >> 1;
 
            // Check for condition
            // to qualify for next round
            if ((mid * 2 + (y - mid)) >= x)
                high = mid - 1;
            else
                low = mid + 1;
        }
        return low;
    }
     
    let x = 6, y = 5;
    document.write(findMinimum(x, y));
 
</script>

1

Complejidad de tiempo: O(log y), como estamos usando la búsqueda binaria en cada recorrido, estamos reduciendo efectivamente a la mitad el tiempo, por lo que el costo será 1+1/2+1/4+…..+1/2^yque es equivalente a log y.

Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.