Minimum matches the team needs to win to qualify

Namachila November 19, 2025

0 0 4 minutes read

Given two integers X and Y where X denotes the number of points required to qualify and Y denotes the number of matches left. The team receives 2 points for winning the match and 1 point for losing. The task is to find the minimum number of matches the team needs to win in order to qualify for the next round.
Examples:

Input: X = 10, Y = 5
Output: 5
The team needs to win all the matches in order to get 10 points.
Input : X = 6, Y = 5
Output : 1
If the team wins a single match and loses the rest 4 matches, they would still qualify.

A naive approach is to check by iterating over all values from 0 to Y and find out the first value which gives us X points.
An efficient approach is to perform a binary search on the number of matches to be won to find out the minimum number of the match. Initially low = 0 and high = X, and then we check for the condition (mid * 2 + (y – mid)) ? x. If the condition prevails, then check if any lower value exists in the left half i.e. high = mid – 1 else check in the right half i.e. low = mid + 1.
Below is the implementation of the above approach:

C++

// 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

// 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

# 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#

// 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
// 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
?>

Javascript

<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>

Output:

Time Complexity: O(log y), as we are using binary search in each traversal we are effectively reducing by half time, so the cost will be 1+1/2+1/4+…..+1/2^ywhich is equivalent to log y.

Auxiliary Space: O(1), as we are not using any extra space.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!