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 roundint 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 Codeint main(){Â Â Â Â int x = 6, y = 5;Â Â Â Â cout << findMinimum(x, y);Â
    return 0;} |
Java
// Java implementation of the approachimport java.io.*;Â
class GFG {Â Â Â Â Â // Function to return the minimum number of// matches to win to qualify for next roundstatic 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 Codepublic 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 rounddef 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 Codeif __name__ == '__main__':Â Â Â Â x = 6Â Â Â Â y = 5Â Â Â Â print(findMinimum(x, y))Â Â Â Â Â # This code is contributed by # Surendra_Gangwar |
C#
// C# implementation of the approachusing System;Â
class GFG{Â Â Â Â Â Â Â Â Â // Function to return the minimum number of// matches to win to qualify for next roundstatic 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 codestatic 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 roundfunction 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> |
1
Â
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.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
