Dada la cantidad de partidos jugados, encuentre la cantidad de equipos en el torneo

Dado un entero M que es el número de partidos jugados en un torneo y cada equipo participante ha jugado un partido con todos los demás equipos. La tarea es encontrar cuántos equipos hay en el torneo.
Ejemplos: 
 

Entrada: M = 3 
Salida: 3 
Si hay 3 equipos A, B y C entonces 
A jugará un partido con B y C 
B jugará un partido con C (B ya ha jugado un partido con A) 
C ya ha jugado partidos con el equipo A y B 
El total de partidos jugados son 3
Entrada: M = 45 
Salida: 10 
 

Planteamiento: Ya que cada partido se juega entre dos equipos. Entonces, este problema es similar a seleccionar 2 objetos de N objetos dados. Por tanto, el número total de partidos será C(N, 2), donde N es el número de equipos participantes. Por lo tanto, 
 

M = C(N, 2) 
M = (N * (N – 1)) / 2 
N ² – N – 2 * M = 0 
Esta es una ecuación cuadrática de tipo ax ² + bx + c = 0. Aquí a = 1, b = -1, c = 2 * M. Por lo tanto, aplicando la fórmula 
x = (-b + sqrt(b ² – 4ac)) / 2a y x = (-b – sqrt(b ² – 4ac)) / 2a 
N = [(-1 * -1) + sqrt((-1 * -1) – (4 * 1 * (-2 * M)))] / 2 
N = (1 + sqrt(1 + (8 * M ))) / 2 y N = (1 – sqrt(1 + (8 * M))) / 2 
 

Después de resolver las dos ecuaciones anteriores, obtendremos dos valores de N. Un valor será positivo y otro negativo. Ignorar el valor negativo. Por tanto, el número de equipos será la raíz positiva de la ecuación anterior.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <cmath>
#include <iostream>
using namespace std;
 
// Function to return the number of teams
int number_of_teams(int M)
{
    // To store both roots of the equation
    int N1, N2, sqr;
 
    // sqrt(b^2 - 4ac)
    sqr = sqrt(1 + (8 * M));
 
    // First root (-b + sqrt(b^2 - 4ac)) / 2a
    N1 = (1 + sqr) / 2;
 
    // Second root (-b - sqrt(b^2 - 4ac)) / 2a
    N2 = (1 - sqr) / 2;
 
    // Return the positive root
    if (N1 > 0)
        return N1;
    return N2;
}
 
// Driver code
int main()
{
    int M = 45;
    cout << number_of_teams(M);
 
    return 0;
}

// Java implementation of the approach
import java.io.*;
 
class GFG
{
 
// Function to return the number of teams
static int number_of_teams(int M)
{
    // To store both roots of the equation
    int N1, N2, sqr;
 
    // sqrt(b^2 - 4ac)
    sqr = (int)Math.sqrt(1 + (8 * M));
 
    // First root (-b + sqrt(b^2 - 4ac)) / 2a
    N1 = (1 + sqr) / 2;
 
    // Second root (-b - sqrt(b^2 - 4ac)) / 2a
    N2 = (1 - sqr) / 2;
 
    // Return the positive root
    if (N1 > 0)
        return N1;
    return N2;
}
 
    // Driver code
    public static void main (String[] args)
    {
        int M = 45;
        System.out.println( number_of_teams(M));
    }
}
 
// this code is contributed by vt_m..

# Python implementation of the approach
import math
 
# Function to return the number of teams
def number_of_teams(M):
     
    # To store both roots of the equation
    N1, N2, sqr = 0,0,0
 
    # sqrt(b^2 - 4ac)
    sqr = math.sqrt(1 + (8 * M))
 
    # First root (-b + sqrt(b^2 - 4ac)) / 2a
    N1 = (1 + sqr) / 2
 
    # Second root (-b - sqrt(b^2 - 4ac)) / 2a
    N2 = (1 - sqr) / 2
 
    # Return the positive root
    if (N1 > 0):
        return int(N1)
    return int(N2)
 
# Driver code
def main():
    M = 45
    print(number_of_teams(M))
if __name__ == '__main__':
    main()
     
# This code has been contributed by 29AjayKumar

// C# implementation of the approach
using System;
 
class GFG
{
 
    // Function to return the number of teams
    static int number_of_teams(int M)
    {
        // To store both roots of the equation
        int N1, N2, sqr;
     
        // sqrt(b^2 - 4ac)
        sqr = (int)Math.Sqrt(1 + (8 * M));
     
        // First root (-b + sqrt(b^2 - 4ac)) / 2a
        N1 = (1 + sqr) / 2;
     
        // Second root (-b - sqrt(b^2 - 4ac)) / 2a
        N2 = (1 - sqr) / 2;
     
        // Return the positive root
        if (N1 > 0)
            return N1;
        return N2;
    }
     
    // Driver code
    public static void Main()
    {
        int M = 45;
        Console.WriteLine( number_of_teams(M));
    }
}
 
// This code is contributed by Ryuga

<?php
// PHP implementation of the approach
 
// Function to return the number of teams
function number_of_teams($M)
{
    // To store both roots of the equation
 
    // sqrt(b^2 - 4ac)
    $sqr = sqrt(1 + (8 * $M));
 
    // First root (-b + sqrt(b^2 - 4ac)) / 2a
    $N1 = (1 + $sqr) / 2;
 
    // Second root (-b - sqrt(b^2 - 4ac)) / 2a
    $N2 = (1 - $sqr) / 2;
 
    // Return the positive root
    if ($N1 > 0)
        return $N1;
    return $N2;
}
 
// Driver code
$M = 45;
echo number_of_teams($M);
 
// This code is contributed
// by chandan_jnu
?>

<script>
// javascript implementation of the approach
 
    // Function to return the number of teams
    function number_of_teams(M) {
        // To store both roots of the equation
        var N1, N2, sqr;
 
        // sqrt(b^2 - 4ac)
        sqr = parseInt( Math.sqrt(1 + (8 * M)));
 
        // First root (-b + sqrt(b^2 - 4ac)) / 2a
        N1 = (1 + sqr) / 2;
 
        // Second root (-b - sqrt(b^2 - 4ac)) / 2a
        N2 = (1 - sqr) / 2;
 
        // Return the positive root
        if (N1 > 0)
            return N1;
        return N2;
    }
 
    // Driver code
     
        var M = 45;
        document.write(number_of_teams(M));
 
// This code contributed by gauravrajput1
</script>

10

 Complejidad de tiempo: O(logn)
Espacio auxiliar: O(1)