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