Encuentra la permutación con resto máximo Suma

Dado un número entero N , la tarea es encontrar una permutación de los números enteros de 1 a N tal que  sea máxima.

Ejemplos: 

Input: N = 3 
Output: 3 1 2 
Sum of the remainder values is (0 + 1 + 2) = 3 
which is the maximum possible.

Input: N = 5 
Output: 5 1 2 3 4 

Acercarse:

Como se sabe, el valor máximo de un número X después de hacer el mod con Y es Y-1 . La permutación que producirá la suma máxima de los valores del módulo será {N, 1, 2, 3, …., N – 1} . Después de evaluar la expresión  en la array anterior, la array de salida será {0, 1, 2, 3, …., N – 1} y este es el valor máximo que se puede obtener.

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 find the permutation
vector<int> Findpermutation(int n)
{
    vector<int> a(n + 1);
 
    // Put n at the first index 1
    a[1] = n;
 
    // Put all the numbers from
    // 2 to n sequentially
    for (int i = 2; i <= n; i++)
        a[i] = i - 1;
 
    return a;
}
 
// Driver code
int main()
{
    int n = 8;
 
    vector<int> v = Findpermutation(n);
 
    // Display the permutation
    for (int i = 1; i <= n; i++)
        cout << v[i] << ' ';
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
class GFG
{
 
// Function to find the permutation
static int[] Findpermutation(int n)
{
    int [] a = new int[n + 1];
 
    // Put n at the first index 1
    a[1] = n;
 
    // Put all the numbers from
    // 2 to n sequentially
    for (int i = 2; i <= n; i++)
        a[i] = i - 1;
 
    return a;
}
 
// Driver code
public static void main(String[] args)
{
    int n = 8;
 
    int []v = Findpermutation(n);
 
    // Display the permutation
    for (int i = 1; i <= n; i++)
        System.out.print(v[i] + " ");
}
}
 
// This code is contributed by 29AjayKumar

# Python3 implementation of the approach
 
# Function to find the permutation
def Findpermutation(n) :
 
    a = [0] * (n + 1);
 
    # Put n at the first index 1
    a[1] = n;
 
    # Put all the numbers from
    # 2 to n sequentially
    for i in range(2, n + 1) :
        a[i] = i - 1;
 
    return a;
 
# Driver code
if __name__ == "__main__" :
 
    n = 8;
 
    v = Findpermutation(n);
 
    # Display the permutation
    for i in range(1, n + 1) :
        print(v[i], end = ' ');
 
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
 
class GFG
{
 
// Function to find the permutation
static int[] Findpermutation(int n)
{
    int [] a = new int[n + 1];
 
    // Put n at the first index 1
    a[1] = n;
 
    // Put all the numbers from
    // 2 to n sequentially
    for (int i = 2; i <= n; i++)
        a[i] = i - 1;
 
    return a;
}
 
// Driver code
public static void Main(String[] args)
{
    int n = 8;
 
    int []v = Findpermutation(n);
 
    // Display the permutation
    for (int i = 1; i <= n; i++)
        Console.Write(v[i] + " ");
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript implementation of the approach
 
// Function to find the permutation
function Findpermutation(n)
{
    let a = new Array(n + 1);
 
    // Put n at the first index 1
    a[1] = n;
 
    // Put all the numbers from
    // 2 to n sequentially
    for (let i = 2; i <= n; i++)
        a[i] = i - 1;
 
    return a;
}
 
// Driver code
    let n = 8;
 
    let v = Findpermutation(n);
 
    // Display the permutation
    for (let i = 1; i <= n; i++)
        document.write(v[i] + ' ');
 
</script>

8 1 2 3 4 5 6 7

Complejidad de tiempo: O(N), Complejidad de espacio: O(N)