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!
