Número de movimientos necesarios para adivinar una permutación.

Dado un número entero N y hay una permutación oculta (de números del 1 al N , cada uno de los cuales ocurre exactamente una vez) que debe adivinar. Puedes hacer lo siguiente: 

Elija un número en la primera posición: 

• Si es correcto, adivina la siguiente posición.
• Si es incorrecto, toda la permutación se restablece y vuelves a adivinar la primera posición.

Puede realizar prueba y error para llegar a la permutación correcta, también puede usar su conocimiento previo para las próximas conjeturas. es decir, si conoce correctamente el número de la primera posición y se equivoca en la segunda posición, en el próximo movimiento puede ingresar la primera posición correctamente y pasar a la segunda posición. 

Encuentre la cantidad mínima de movimientos que se necesitarían en el peor de los casos para obtener la permutación completa correcta.

Ejemplos:  

Entrada: N = 2 
Salida: 3 
Elige 2 para la primera posición y la permutación se restablece. 
Eliges 1 para la primera posición, la suposición es correcta y ahora debes adivinar la segunda posición. 
Eliges 2 para la segunda posición ya que esa es la única opción que te queda.

Entrada: N = 3 
Salida: 7 
 

Enfoque: Para adivinar correctamente la i-ésima posición, se necesitarían (ni) conjeturas. Y para cada suposición, necesitaría sumar un total de i movimientos ((i-1) movimientos para ingresar el prefijo correcto que ya conoce y 1 movimiento para adivinar el actual). En el paso final, le tomaría N movimientos más ingresar la permutación correcta.

A continuación se muestra la implementación del enfoque anterior:  

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns the required moves
int countMoves(int n)
{
    int ct = 0;
    for (int i = 1; i <= n; i++)
        ct += i * (n - i);
 
    // Final move
    ct += n;
    return ct;
}
 
// Driver Program to test above function
int main()
{
    int n = 3;
    cout << countMoves(n);
    return 0;
}

// Java implementation of the approach
 
import java.io.*;
 
class GFG {
 
 
// Function that returns the required moves
static int countMoves(int n)
{
    int ct = 0;
    for (int i = 1; i <= n; i++)
        ct += i * (n - i);
 
    // Final move
    ct += n;
    return ct;
}
 
// Driver Program to test above function
 
 
    public static void main (String[] args) {
        int n = 3;
    System.out.println( countMoves(n));
    }
}
// This code is contributed by anuj_67..

# Python3 implementation of the approach
 
# Function that returns the
# required moves
def countMoves(n):
 
    ct = 0
    for i in range(1, n + 1):
        ct += i * (n - i)
 
    # Final move
    ct += n
    return ct
 
# Driver Code
if __name__ == "__main__":
    n = 3
    print(countMoves(n))
 
# This code is contributed
# by ChitraNayal

// C# implementation of the approach
using System;
class GFG {
 
    // Function that returns the required moves
    static int countMoves(int n)
    {
        int ct = 0;
        for (int i = 1; i <= n; i++)
            ct += i * (n - i);
     
        // Final move
        ct += n;
        return ct;
    }
     
    // Driver Program to test above function
    static void Main()
    {
        int n = 3;
        Console.WriteLine(countMoves(n));
    }
     
    // This code is contributed by Ryuga.
 
}

<?php
// PHP implementation of the approach
 
// Function that returns the
// required moves
function countMoves($n)
{
    $ct = 0;
    for ($i = 1; $i <= $n; $i++)
        $ct += $i * ($n - $i);
 
    // Final move
    $ct += $n;
    return $ct;
}
 
// Driver Code
$n = 3;
echo countMoves($n);
 
// This code is contributed
// by Akanksha Rai
?>

<script>
 
// Javascript implementation of the approach
 
// Function that returns the required moves
function countMoves(n)
{
    let ct = 0;
    for(let i = 1; i <= n; i++)
        ct += i * (n - i);
 
    // Final move
    ct += n;
    return ct;
}
 
// Driver code
let n = 3;
 
document.write(countMoves(n));
 
// This code is contributed by Mayank Tyagi
     
</script>

7

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(1)