Genere una array de longitud N que tenga K subarreglos como permutaciones de su propia longitud

Dados los números enteros N y K , la tarea es generar una array de longitud N que contenga exactamente K subarreglos como una permutación de 1 a X , donde X es la longitud del subarreglo. Puede haber varias respuestas, puede imprimir cualquiera de ellas. Si no es posible construir una array, imprima -1 .

Nota: una permutación de longitud N es una lista de números enteros del 1 al N (inclusive) donde cada elemento aparece exactamente una vez.

Ejemplos:

Entrada: N = 5, K = 4
Salida: 1, 2, 3, 5, 4
Explicación: 4 subarreglos que son una permutación de su propia longitud son:
A[1] = {1}
A[1…2] = { 1, 2}
A[1…3] = {1, 2, 3}
A[1…5] = {1, 2, 3, 5, 4}
Tenga en cuenta que no existe ninguna permutación de longitud 4 como subarreglo.              

Entrada: N = 7, K = 3
Salida: {1, 2, 7, 4, 5, 6, 3}
Explicación: 3 subarreglos que son una permutación de su propia longitud son: 
A[1] = {1}
A[ 1…2] = {1, 2}
A[1…7] = {1, 2, 7, 3, 4, 5, 6}
No existen permutaciones de longitudes 3, 4, 5 y 6 como un subarreglo.

Planteamiento: La solución al problema se basa en la siguiente observación. Si todos los números están dispuestos en orden creciente de 1 a N , entonces hay un total de N subarreglos como permutaciones de su propia longitud. Si cualquier valor se intercambia con el valor más alto, el número de permutaciones disminuye. Entonces, para hacer que el número sea igual a K , hacer que el valor de Kth sea el más alto y mantener a los demás cada vez más ordenados cumplirá la tarea. Si N > 1 , hay al menos 2 subarreglos que son permutaciones de su propia longitud. Siga los pasos que se mencionan a continuación para resolver el problema:

• Si N > 1 y K < 2 o si K = 0 , entonces tal arreglo no es posible.
• Genere una array de longitud N que consta de números enteros del 1 al N en orden ordenado.
• El elemento máximo en la array obviamente será el último elemento N que es arr[N-1] .
• Intercambiar arr[N-1] con arr[K-1]
• La array es una respuesta posible.

Ilustración: 

Por ejemplo, tome N = 5, K = 4

• Generar una array que contiene de 1 a N en orden ordenado.
  arr[] = {1, 2, 3, 4, 5}
  Hay 5 subarreglos que son permutaciones de su propia longitud: {1}, {1, 2}, {1, 2, 3}, {1, 2, 3, 4}, {1, 2, 3, 4, 5}
• Aquí K requerido es 4 . Así que cambia el cuarto elemento con el valor más alto.
  arr[] = {1, 2, 3, 5, 4}
  Ahora solo hay K subarreglos que son permutaciones de su propia longitud: {1}, {1, 2}, {1, 2, 3}, {1, 2, 3, 4, 5}.
  Debido a que el valor máximo llega a la posición Kth y ahora 
  para subarreglos de longitud K o mayor (pero menor que N ), el elemento más alto se incluye en el subarreglo 
  que no forma parte de una permutación que contiene elementos de 1 a X (longitud del subarreglo).

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

// C++ program to implement the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to generate the required array
vector<int> generateArray(int N, int K)
{
    vector<int> arr;
     
    // If making an array is not possible
    if (K == 0 || (N > 1 && K < 2))
        return arr;
    arr.assign(N, 0);
     
    // Array of size N in sorted order
    for (int i = 1; i <= N; i++)
        arr[i - 1] = i;
 
    // Swap the maximum with the Kth element
    swap(arr[K - 1], arr[N - 1]);
    return arr;
}
 
// Driver code
int main()
{
    int N = 5, K = 4;
 
    // Function call
    vector<int> ans = generateArray(N, K);
    if (ans.size() == 0)
        cout << "-1";
    else {
        for (int i : ans)
            cout << i << " ";
    }
    return 0;
}

// Java code for the above approach
import java.util.*;
class GFG{
 
  // Function to swap two numbers
  static void swap(int m, int n)
  {
    // Swapping the values
    int temp = m;
    m = n;
    n = temp;
  }
 
  // Function to generate the required array
  static int[] generateArray(int N, int K)
  {
    int[] arr = new int[N];
 
    // If making an array is not possible
    if (K == 0 || (N > 1 && K < 2))
      return arr;
    for (int i = 0; i < N; i++) {
      arr[i] = 0;
    }
 
    // Array of size N in sorted order
    for (int i = 1; i <= N; i++)
      arr[i - 1] = i;
 
    // Swap the maximum with the Kth element
    swap(arr[K - 1], arr[N - 1]);
    return arr;
  }
 
  // Driver code
  public static void main(String[] args)
  {
 
    int N = 5, K = 4;
 
    // Function call
    int[] ans = generateArray(N, K);
    if (ans.length == 0)
      System.out.print("-1");
    else {
      for (int i = 0; i < ans.length; i++) {
        System.out.print(ans[i] + " ");
      }
    }
  }
}
 
// This code is contributed by sanjoy_62.

# Python program to implement the approach
 
# Function to generate the required array
def generateArray(N,  K):
    arr = []
 
    # If making an array is not possible
    if (K == 0 or (N > 1 and K < 2)):
        return arr
 
    for i in range(0, N):
        arr.append(0)
 
    # Array of size N in sorted order
    for i in range(1, N + 1):
        arr[i-1] = i
 
    # Swap the maximum with the Kth element
    arr[K - 1], arr[N - 1] = arr[N - 1], arr[K - 1]
    return arr
 
 
# Driver code
N = 5
K = 4
 
# Function call
ans = generateArray(N, K)
if (len(ans) == 0):
    print("-1")
else:
    for i in ans:
        print(i, end=' ')
 
        # This code is contributed by ninja_hattori.

// C# program to implement the approach
using System;
class GFG {
 
  // Function to swap two numbers
  static void swap(int m, int n)
  {
    // Swapping the values
    int temp = m;
    m = n;
    n = temp;
  }
 
  // Function to generate the required array
  static int[] generateArray(int N, int K)
  {
    int[] arr = new int[N];
 
    // If making an array is not possible
    if (K == 0 || (N > 1 && K < 2))
      return arr;
    for (int i = 0; i < N; i++) {
      arr[i] = 0;
    }
 
    // Array of size N in sorted order
    for (int i = 1; i <= N; i++)
      arr[i - 1] = i;
 
    // Swap the maximum with the Kth element
    swap(arr[K - 1], arr[N - 1]);
    return arr;
  }
 
  // Driver code
  public static void Main()
  {
    int N = 5, K = 4;
 
    // Function call
    int[] ans = generateArray(N, K);
    if (ans.Length == 0)
      Console.Write("-1");
    else {
      for (int i = 0; i < ans.Length; i++) {
        Console.Write(ans[i] + " ");
      }
    }
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
// JavaScript code for the above approach
 
// Function to generate the required array
function generateArray( N, K)
{
    let arr ;
     
    // If making an array is not possible
    if (K == 0 || (N > 1 && K < 2))
        return [];
    arr = new Array(N).fill(0);
     
    // Array of size N in sorted order
    for (let i = 1; i <= N; i++)
        arr[i - 1] = i;
 
    // Swap the maximum with the Kth element
    let temp = arr[K - 1];
     arr[K - 1] = arr[N-1];
     arr[N-1] = temp
    return arr;
}
 
// Driver code
    let N = 5, K = 4;
 
    // Function call
   let ans = generateArray(N, K);
    if (ans.length == 0)
        document.write("-1");
    else {
        for (let i of ans)
            document.write( i  + " ");
    }
     
       // This code is contributed by Potta Lokesh
    </script>

1 2 3 5 4 

Complejidad temporal: O(N)
Espacio auxiliar: O(N)