Dados dos enteros positivos N y K , la tarea es construir una permutación de los primeros N números naturales tal que todas las posibles diferencias absolutas entre elementos adyacentes sean K .
Ejemplos:
Entrada: N = 3, K = 1
Salida: 1 2 3
Explicación: Considerando la permutación {1, 2, 3}, todas las posibles diferencias absolutas únicas de elementos adyacentes son {1}. Dado que la cuenta es 1(= K), imprima la secuencia {1, 2, 3} como la permutación resultante.Entrada: N = 3, K = 2
Salida: 1 3 2
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es crear una array con elementos del 1 al N dispuestos en orden ascendente y luego atravesar los primeros K elementos de la array e invertir el subarreglo comenzando en el índice actual y terminando en el último. índice. Después de completar los pasos anteriores, imprima la array resultante obtenida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to reverse the given list
void reverse(int list[], int start, int end)
{
// Iterate until start < end
while (start < end)
{
// Swap operation
int temp = list[start];
list[start] = list[end];
list[end] = temp;
start++;
end--;
}
}
// Function to construct a list with
// exactly K unique adjacent element
// differences
void makeList(int N, int K)
{
// Stores the resultant array
int list[N];
// Add initial value to array
for(int i = 1; i <= N; i++)
{
list[i - 1] = i;
}
// Reverse the list k-1 times
// from index i to n-1
for(int i = 1; i < K; i++)
{
reverse(list, i, N - 1);
}
// Print the resultant array
for(int i = 0; i < N; i++)
{
cout << list[i] << " ";
}
}
// Driver code
int main()
{
int N = 6, K = 3;
makeList(N, K);
return 0;
}
// This code is contributed by mohit kumar 29
Java
// Java program for the above approach
class GFG {
// Function to construct a list with
// exactly K unique adjacent element
// differences
public static void makeList(int N, int K)
{
// Stores the resultant array
int[] list = new int[N];
// Add initial value to array
for (int i = 1; i <= N; i++) {
list[i - 1] = i;
}
// Reverse the list k-1 times
// from index i to n-1
for (int i = 1; i < K; i++) {
reverse(list, i, N - 1);
}
// Print the resultant array
for (int i = 0;
i < list.length; i++) {
System.out.print(list[i] + " ");
}
}
// Function to reverse the given list
public static void reverse(
int[] list, int start, int end)
{
// Iterate until start < end
while (start < end) {
// Swap operation
int temp = list[start];
list[start] = list[end];
list[end] = temp;
start++;
end--;
}
}
// Driver Code
public static void main(
String[] args)
{
int N = 6, K = 3;
makeList(N, K);
}
}
Python3
# Python 3 program for the above approach # Function to reverse the given lst def reverse(lst, start, end): # Iterate until start < end while (start < end): # Swap operation temp = lst[start] lst[start] = lst[end] lst[end] = temp start += 1 end -= 1 # Function to construct a lst with # exactly K unique adjacent element # differences def makelst(N, K): # Stores the resultant array lst = [0 for i in range(N)] # Add initial value to array for i in range(1, N + 1, 1): lst[i - 1] = i # Reverse the lst k-1 times # from index i to n-1 for i in range(1, K, 1): reverse(lst, i, N - 1) # Print the resultant array for i in range(N): print(lst[i], end = " ") # Driver code if __name__ == '__main__': N = 6 K = 3 makelst(N, K) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# program for the above approach
using System;
class GFG{
// Function to construct a list with
// exactly K unique adjacent element
// differences
public static void makeList(int N, int K)
{
// Stores the resultant array
int[] list = new int[N];
// Add initial value to array
for(int i = 1; i <= N; i++)
{
list[i - 1] = i;
}
// Reverse the list k-1 times
// from index i to n-1
for(int i = 1; i < K; i++)
{
reverse(list, i, N - 1);
}
// Print the resultant array
for(int i = 0; i < list.Length; i++)
{
Console.Write(list[i] + " ");
}
}
// Function to reverse the given list
public static void reverse(int[] list, int start,
int end)
{
// Iterate until start < end
while (start < end)
{
// Swap operation
int temp = list[start];
list[start] = list[end];
list[end] = temp;
start++;
end--;
}
}
// Driver Code
static public void Main()
{
int N = 6, K = 3;
makeList(N, K);
}
}
// This code is contributed by Dharanendra L V.
Javascript
<script>
// Javascript program for the above approach
// Function to construct a list with
// exactly K unique adjacent element
// differences
function makeList(N, K)
{
// Stores the resultant array
let list = Array.from(Array(N), ()=>Array(0));
// Add initial value to array
for (let i = 1; i <= N; i++) {
list[i - 1] = i;
}
// Reverse the list k-1 times
// from index i to n-1
for (let i = 1; i < K; i++) {
reverse(list, i, N - 1);
}
// Print the resultant array
for (let i = 0;
i < list.length; i++) {
document.write(list[i] + " ");
}
}
// Function to reverse the given list
function reverse(
list, start, end)
{
// Iterate until start < end
while (start < end) {
// Swap operation
let temp = list[start];
list[start] = list[end];
list[end] = temp;
start++;
end--;
}
}
// Driver Code
let N = 6, K = 3;
makeList(N, K);
// This code is contributed by sanjoy_62.
</script>
Producción:
1 6 2 3 4 5
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente: el enfoque anterior también se puede optimizar utilizando el enfoque de dos puntos . Siga los pasos a continuación para resolver el problema:
- Inicialice una array ans[] de tamaño N , que almacena la permutación resultante.
- Cree dos variables, digamos izquierda y derecha como 1 y N respectivamente .
- Recorra la array dada y realice los siguientes pasos:
- Si el valor de K es par, empuje el valor de la izquierda a la array ans[] e incremente el valor de la izquierda en 1 .
- Si el valor de K es impar, empuje el valor de la derecha a la array ans[] y disminuya el valor de la derecha en 1 .
- Si el valor de K es mayor que 1, entonces disminuya el valor de K en 1 .
- Después de completar los pasos anteriores, imprima la array ans[] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;
// Function to construct the list
// with exactly K unique adjacent
// element differences
void makeList(int N, int K)
{
// Stores the resultant array
int list[N];
// Stores the left and the right
// most element of the range
int left = 1;
int right = N;
// Traverse the array
for (int i = 0; i < N; i++) {
// If k is even, the add
// left to array and
// increment the left
if (K % 2 == 0) {
list[i] = left;
left = left + 1;
}
// If k is odd, the add
// right to array and
// decrement the right
else {
list[i] = right;
right = right - 1;
}
// Repeat the steps for
// k-1 times
if (K > 1)
K--;
}
// Print the resultant list
for (int i = 0; i < N; i++) {
cout<<list[i]<< " ";
}
}
// Driver Code
int main()
{
int N = 6;
int K = 3;
makeList(N, K);
}
// This code is contributed by ukasp.
Java
// Java program for the above approach
class GFG {
// Function to construct the list
// with exactly K unique adjacent
// element differences
public static void makeList(int N,
int K)
{
// Stores the resultant array
int[] list = new int[N];
// Stores the left and the right
// most element of the range
int left = 1;
int right = N;
// Traverse the array
for (int i = 0; i < N; i++) {
// If k is even, the add
// left to array and
// increment the left
if (K % 2 == 0) {
list[i] = left;
left = left + 1;
}
// If k is odd, the add
// right to array and
// decrement the right
else {
list[i] = right;
right = right - 1;
}
// Repeat the steps for
// k-1 times
if (K > 1)
K--;
}
// Print the resultant list
for (int i = 0;
i < list.length; i++) {
System.out.print(
list[i] + " ");
}
}
// Driver Code
public static void main(String[] args)
{
int N = 6;
int K = 3;
makeList(N, K);
}
}
Python3
# Python3 program for the above approach # Function to construct the lst # with exactly K unique adjacent # element differences def makelst(N, K): # Stores the resultant array lst = [0 for i in range(N)] # Stores the left and the right # most element of the range left = 1 right = N # Traverse the array for i in range(N): # If k is even, the add # left to array and # increment the left if (K % 2 == 0): lst[i] = left left = left + 1 # If k is odd, the add # right to array and # decrement the right else: lst[i] = right right = right - 1 # Repeat the steps for # k-1 times if (K > 1): K -= 1 # Print the resultant lst for i in range(N): print(lst[i], end = " ") # Driver Code if __name__ == '__main__': N = 6 K = 3 makelst(N, K) # This code is contributed by bgangwar59
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to construct the list
// with exactly K unique adjacent
// element differences
public static void makeList(int N, int K)
{
// Stores the resultant array
int[] list = new int[N];
// Stores the left and the right
// most element of the range
int left = 1;
int right = N;
// Traverse the array
for(int i = 0; i < N; i++)
{
// If k is even, the add
// left to array and
// increment the left
if (K % 2 == 0)
{
list[i] = left;
left = left + 1;
}
// If k is odd, the add
// right to array and
// decrement the right
else
{
list[i] = right;
right = right - 1;
}
// Repeat the steps for
// k-1 times
if (K > 1)
K--;
}
// Print the resultant list
for(int i = 0; i < list.Length; i++)
{
Console.Write(list[i] + " ");
}
}
// Driver Code
public static void Main(String[] args)
{
int N = 6;
int K = 3;
makeList(N, K);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for the above approach
// Function to construct the list
// with exactly K unique adjacent
// element differences
function makeList(N, K)
{
// Stores the resultant array
var list= new Array(N);
// Stores the left and the right
// most element of the range
var left = 1;
var right = N;
// Traverse the array
for(var i = 0; i < N; i++)
{
// If k is even, the add
// left to array and
// increment the left
if (K % 2 == 0)
{
list[i] = left;
left = left + 1;
}
// If k is odd, the add
// right to array and
// decrement the right
else
{
list[i] = right;
right = right - 1;
}
// Repeat the steps for
// k-1 times
if (K > 1)
K--;
}
// Print the resultant list
for(var i = 0; i < N; i++)
{
document.write(list[i] + " ");
}
}
// Driver code
var N = 6;
var K = 3;
makeList(N, K);
// This code is contributed by SoumikMondal
</script>
Producción:
6 1 5 4 3 2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por hritikrommie y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA