Maximum points difference between the winner and runner up of Tournament

0 0 3 minutes read

Given integer N and K, denoting the number of teams participating in a football tournament where each team plays only one match with each other team, the task is to find the maximum point difference between the winner and the runner-up (second place holder) of the tournament where the winner of a match gets K points.

Examples:

Input: N = 2, K = 4
Output: 4
Explanation: If there are 2 team A and B then either A will win or lose.
If A wins the match it scores 4 points and team B score is 0.
Hence maximum possible difference of points between the winning team and the second-placed team is 4 .

Input: N = 3, K = 4
Output: 4

Input: N = 9, K = 5
Output: 20

Approach: the problem can be solved based on the following mathematical observation:

The difference will be maximum when the winner wins all the matches it plays and all the other teams win near equal matches each. As each time is playing against others only once so the total number of matches is N * (N – 1)/2.

If the winner wins all matches (i.e., (N-1) matches that it plays) the remaining number of matches are:
(N * (N – 1))/2 – (N – 1) = (N – 1) * (N – 2) / 2.
If each team wins near equal matches, the runner-up will win ceil[ (N – 1)*(N – 2) / (2 * (N – 1)) ] = ceil[ (N – 2)/2 ]

If N is odd: The value is (N – 2 + 1)/2 = (N – 1)/2
If N is even: The value is (N – 2)/2.

Matches difference when N is odd: (N – 1) – (N – 1)/2 = (N – 1)/2. So points difference = K * ((N – 1)/2).
Matches difference when N is even: (N – 1) – (N – 2)/2 = N/2. So points difference = K * (N / 2).

Follow the steps mentioned below to implement the idea:

Check if N is odd or even.
If N is odd the required difference is K*((N-1)/2).
If N is even the required difference is K*(N/2).

Below is the implementation of the above approach.

C++

// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate point difference
int pointDiff(int N, int K)
{
 
  // If N is odd
  if (N % 3 != 0)
    return ((N - 1) / 2) * K;
 
  // If N is even
  return (N / 2) * K;
}
 
// Driver code
int main()
{
  int N = 9, K = 5;
 
  // Function call
  cout << pointDiff(N, K);
 
  return 0;
}
 
// This code is contributed by rakeshsahni

Java

// Java code to implement the approach
 
import java.util.*;
 
class GFG {
 
    // Function to calculate point difference
    public static int pointDiff(int N, int K)
    {
        // If N is odd
        if (N % 3 != 0)
            return ((N - 1) / 2) * K;
 
        // If N is even
        return (N / 2) * K;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int N = 9, K = 5;
 
        // Function call
        System.out.println(pointDiff(N, K));
    }
}

Python3

# Python code to implement the approach
 
# Function to calculate point difference
def pointDiff(N, K):
   
    # If N is odd
    if N % 3 != 0:
        return ((N - 1) // 2) * K
       
    # If N is even
    return (N // 2) * K
 
# Driver code
if __name__ == "__main__":
    N = 9
    K = 5
    # Function call
    print(pointDiff(N, K))
 
# This code is contributed by Rohit Pradhan

C#

// C# code to implement the approach
using System;
using System.Linq;
 
public class GFG
{
  // Function to calculate point difference
  public static int pointDiff(int N, int K)
  {
    // If N is odd
    if (N % 3 != 0)
      return ((N - 1) / 2) * K;
 
    // If N is even
    return (N / 2) * K;
  }
 
  // Driver Code
  public static void Main(string[] args)
  {
    int N = 9, K = 5;
 
    // Function call
    Console.WriteLine(pointDiff(N, K));
  }
}
 
// This code is contributed by code_hunt.

Javascript

<script>
 
// JavaScript code to implement the approach
 
 
// Function to calculate point difference
function pointDiff(N, K)
{
 
  // If N is odd
  if (N % 3 != 0)
    return Math.floor((N - 1) / 2) * K;
 
  // If N is even
  return Math.floor(N / 2) * K;
}
 
// Driver code
 
let N = 9, K = 5;
 
// Function call
document.write(pointDiff(N, K),"</br>");
 
 
// This code is contributed by shinjanpatra
 
</script>

Output

Time Complexity: O(1)
Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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!