Operaciones mínimas del tipo dado requeridas para hacer un gráfico completo

Dado N vértice donde N es par . Inicialmente no hay arista entre ninguno de los vértices. 
Se le permite realizar la operación como se ilustra aquí: 
 

• En una sola operación , el total de Nodes se puede dividir en dos grupos y los bordes ( u, v) se pueden dibujar para todos los valores posibles de u y v , de modo que ambos pertenezcan a grupos diferentes.

La tarea es encontrar el número mínimo de operaciones requeridas para convertir estos vértices en un gráfico completo .
Ejemplos: 
 

Entrada: N = 4 
Salida: 2 
Operación 1: Grupos = [1, 2], [3, 4] todos los bordes posibles serán {1-4, 1-3, 2-3, 2-4}. 
Operación 2: Grupos = [1, 3], [2, 4] todos los posibles bordes serán {1-4, 1-3, 2-3, 2-4, 1-2, 3-4}. 
El gráfico es ahora un gráfico completo.
Entrada: N = 10 
Salida: 4 
 

Planteamiento: Un grafo se llamará grafo completo cuando entre cada par de vértices exista una arista. Aquí el problema puede resolverse mediante el enfoque de divide y vencerás . Para realizar el mínimo número de operaciones, divida los vértices en dos grupos cada uno con N/2 vértices y dibuje todas las aristas posibles. Ahora observa que tenemos que crear un borde entre los vértices que ahora están en el mismo grupo. Así que los dividiremos por la mitad y los pondremos en diferentes grupos. 
Estos pasos se repetirán hasta que se hayan dibujado todos los bordes, es decir, al máximo ⌈ log2(N) ⌉ veces, ya que la operación dividirá los bordes en dos mitades de igual tamaño.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return
// the minimum number of steps required
int minOperations(int N)
{
    double x = log2(N);
 
    int ans = ceil(x);
 
    return ans;
}
 
// Driver Code
int main()
{
    int N = 10;
    cout << minOperations(N);
 
    return 0;
}

// Java implementation of the approach
 
class GFG
{
     
    // Function to return the minimum
    // number of steps required
    static int minOperations(int N)
    {
        double x = Math.log(N) / Math.log(2);
     
        int ans = (int)(Math.ceil(x));
     
        return ans;
    }
     
    // Driver Code
    public static void main(String[] args)
    {
        int N = 10;
        System.out.println(minOperations(N));
    }
}
 
// This code is contributed by Ryuga

# Python 3 implementation of the approach
from math import log2, ceil
 
# Function to return the minimum
# number of steps required
def minOperations(N):
    x = log2(N)
 
    ans = ceil(x)
 
    return ans
 
# Driver Code
if __name__ == '__main__':
    N = 10
    print(minOperations(N))
 
# This code is contributed by
# Surendra_Gangwar

// C# implementation of the approach
using System;
class GFG
{
     
// Function to return the minimum
// number of steps required
static int minOperations(int N)
{
    double x = Math.Log(N, 2);
 
    int ans = (int)(Math.Ceiling(x));
 
    return ans;
}
 
// Driver Code
static void Main()
{
    int N = 10;
    Console.WriteLine(minOperations(N));
}
}
 
// This code is contributed by mits

<?php
// PHP implementation of the approach
 
// Function to return the minimum number
// of steps required
function minOperations($N)
{
    $x = log($N, 2);
 
    $ans = ceil($x);
 
    return $ans;
}
 
// Driver Code
$N = 10;
echo minOperations($N);
 
// This code is contributed
// by Akanksha Rai
?>

<script>
// javascript implementation of the approach
 
    // Function to return the minimum
    // number of steps required
    function minOperations(N)
    {
        var x = Math.log(N) / Math.log(2);
        var ans = parseInt( (Math.ceil(x)));
        return ans;
    }
 
    // Driver Code   
    var N = 10;
    document.write(minOperations(N));
 
// This code is contributed by todaysgaurav
</script>

4

Complejidad de tiempo: O(1)

Espacio Auxiliar: O(1)