Dado un entero positivo N , la tarea es construir la array lexicográficamente más grande de tamaño (2 * N – 1) que comprende los primeros N números naturales de modo que cada elemento aparezca dos veces excepto 1 y la repetición de X esté exactamente separada por X distancia en el array construida.
Ejemplos:
Entrada: N = 4
Salida: 4 2 3 2 4 3 1
Explicación:
Para la array generada {4, 2, 3, 2, 4, 3, 1} cada elemento duplicado (digamos X) está a la distancia X.Entrada: N = 5
Salida: 5 3 1 4 3 5 2 4 2
Enfoque: El problema se puede resolver usando Backtracking . La idea es generar todas las permutaciones posibles según la condición dada e imprimir la que satisfaga las condiciones dadas. Siga los pasos a continuación para resolver el problema:
- Inicialice una array, digamos ans[] , de tamaño (2*N – 1) 0 s en cada índice y un HashMap para almacenar todos los elementos asignados a la array construida.
- Defina una función builtArray(i, N) para generar la array resultante realizando los siguientes pasos:
- Si el valor de i es (2*N – 1) , entonces se genera una de las permutaciones posibles. Por lo tanto, devuelve verdadero .
- De lo contrario, si el valor en el índice actual ya está asignado, llame recursivamente a la próxima iteración constructArray(i+1, N) .
- De lo contrario, realice lo siguiente:
- Coloque todos los números no visitados del rango [1, N] a partir de N .
- Si el valor elegido en el paso anterior no conduce a una posible combinación de la array, elimine el valor actual de la array y pruebe otras combinaciones posibles asignando otros elementos del rango.
- Si no se obtiene ninguna combinación posible, devuelve falso .
- Después de completar los pasos anteriores, imprima la array ans[] tal como la obtuvo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++14 program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
const int N = 4;
// Stores the required sequence
vector<int> ans(2 * N - 1, 0);
// Stores the visited and unvisited values
set<int> visited;
// Function to construct the array
// according to the given conditions
bool constructArray(int i)
{
// Base Case
if (i == ans.size()) {
return true;
}
// If a value is already assigned
// at current index, then recursively
// call for the next index
if (ans[i] != 0)
return constructArray(i + 1);
else {
// Iterate over the range[N, 1]
for (int val = N; val >= 1; val--) {
// If the current value is
// already visited, continue
if (visited.find(val) != visited.end())
continue;
// Otherwise, mark this value as
// visited and set ans[i] = val
visited.insert(val);
ans[i] = val;
// If val is equal to 1, then
// recursively call for the
// next index
if (val == 1) {
bool found = constructArray(i + 1);
// If solution is found,
// then return true
if (found)
return true;
}
// For all other values, assign
// ans[i + val] to val if the
// i + val < ans.length
else if (i + val < ans.size()
&& ans[i + val] == 0) {
ans[val + i] = val;
// Recursively call for
// next index to check if
// solution can be found
bool found = constructArray(i + 1);
// If solution is found then
// return true
if (found)
return true;
// BackTracking step
ans[i + val] = 0;
}
// BackTracking step
ans[i] = 0;
visited.erase(val);
}
}
// In all other cases, return false
return false;
}
// Driver code
int main()
{
// Function Call
constructArray(0);
// Print the resultant array
for (int X : ans)
cout << X << " ";
return 0;
}
// This code is contributed by kingash.
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Stores the required sequence
static int ans[];
// Stores the visited and unvisited values
static HashSet<Integer> visited;
// Function to construct the array
// according to the given conditions
public static boolean
constructArray(int i, int N)
{
// Base Case
if (i == ans.length) {
return true;
}
// If a value is already assigned
// at current index, then recursively
// call for the next index
if (ans[i] != 0)
return constructArray(i + 1, N);
else {
// Iterate over the range[N, 1]
for (int val = N; val >= 1; val--) {
// If the current value is
// already visited, continue
if (visited.contains(val))
continue;
// Otherwise, mark this value as
// visited and set ans[i] = val
visited.add(val);
ans[i] = val;
// If val is equal to 1, then
// recursively call for the
// next index
if (val == 1) {
boolean found
= constructArray(i + 1, N);
// If solution is found,
// then return true
if (found)
return true;
}
// For all other values, assign
// ans[i + val] to val if the
// i + val < ans.length
else if (i + val < ans.length
&& ans[i + val] == 0) {
ans[val + i] = val;
// Recursively call for
// next index to check if
// solution can be found
boolean found
= constructArray(i + 1, N);
// If solution is found then
// return true
if (found)
return true;
// BackTracking step
ans[i + val] = 0;
}
// BackTracking step
ans[i] = 0;
visited.remove(val);
}
}
// In all other cases, return false
return false;
}
// Driver Code
public static void main(String[] args)
{
int N = 4;
ans = new int[2 * N - 1];
visited = new HashSet<>();
// Function Call
constructArray(0, N);
// Print the resultant array
for (int X : ans)
System.out.print(X + " ");
}
}
Python3
# Python3 program for the above approach
# Function to construct the array
# according to the given conditions
def constructArray(i, N):
global ans, visited
# Base Case
if (i == len(ans)):
return True
# If a value is already assigned
# at current index, then recursively
# call for the next index
if (ans[i] != 0):
return constructArray(i + 1, N)
else:
# Iterate over the range[N, 1]
for val in range(N, 0, -1):
# If the current value is
# already visited, continue
if (val in visited):
continue
# Otherwise, mark this value as
# visited and set ans[i] = val
visited[val] = 1
ans[i] = val
# If val is equal to 1, then
# recursively call for the
# next index
if (val == 1):
found = constructArray(i + 1, N)
# If solution is found,
# then return true
if (found):
return True
# For all other values, assign
# ans[i + val] to val if the
# i + val < ans.length
elif (i + val < len(ans) and ans[i + val] == 0):
ans[val + i] = val
# Recursively call for
# next index to check if
# solution can be found
found = constructArray(i + 1, N)
# If solution is found then
# return true
if (found):
return True
# BackTracking step
ans[i + val] = 0
# BackTracking step
ans[i] = 0
del visited[val]
# In all other cases, return false
return False
# Driver Code
if __name__ == '__main__':
N = 4
ans = [0]*(2 * N - 1)
visited = {}
# Function Call
constructArray(0, N)
# Print the resultant array
for x in ans:
print(x,end=" ")
# this code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
using System.Linq;
class GFG{
// Stores the required sequence
static int[] ans;
// Stores the visited and unvisited values
static HashSet<int> visited;
// Function to construct the array
// according to the given conditions
public static bool
constructArray(int i, int N)
{
// Base Case
if (i == ans.Length) {
return true;
}
// If a value is already assigned
// at current index, then recursively
// call for the next index
if (ans[i] != 0)
return constructArray(i + 1, N);
else {
// Iterate over the range[N, 1]
for (int val = N; val >= 1; val--) {
// If the current value is
// already visited, continue
if (visited.Contains(val))
continue;
// Otherwise, mark this value as
// visited and set ans[i] = val
visited.Add(val);
ans[i] = val;
// If val is equal to 1, then
// recursively call for the
// next index
if (val == 1) {
bool found
= constructArray(i + 1, N);
// If solution is found,
// then return true
if (found)
return true;
}
// For all other values, assign
// ans[i + val] to val if the
// i + val < ans.length
else if (i + val < ans.Length
&& ans[i + val] == 0) {
ans[val + i] = val;
// Recursively call for
// next index to check if
// solution can be found
bool found
= constructArray(i + 1, N);
// If solution is found then
// return true
if (found)
return true;
// BackTracking step
ans[i + val] = 0;
}
// BackTracking step
ans[i] = 0;
visited.Remove(val);
}
}
// In all other cases, return false
return false;
}
// Driver Code
static public void Main()
{
int N = 4;
ans = new int[2 * N - 1];
visited = new HashSet<int>();
// Function Call
constructArray(0, N);
// Print the resultant array
foreach (int X in ans)
Console.Write(X + " ");
}
}
// This code is contributed by code_hunt.
Javascript
<script>
// JavaScript program for the above approach
// Stores the required sequence
var ans = [];
// Stores the visited and unvisited values
var visited = [];
// Function to construct the array
// according to the given conditions
function constructArray(i, N) {
// Base Case
if (i === ans.length) {
return true;
}
// If a value is already assigned
// at current index, then recursively
// call for the next index
if (ans[i] !== 0) return constructArray(i + 1, N);
else {
// Iterate over the range[N, 1]
for (var val = N; val >= 1; val--) {
// If the current value is
// already visited, continue
if (visited.includes(val)) continue;
// Otherwise, mark this value as
// visited and set ans[i] = val
visited.push(val);
ans[i] = val;
// If val is equal to 1, then
// recursively call for the
// next index
if (val === 1) {
var found = constructArray(i + 1, N);
// If solution is found,
// then return true
if (found) return true;
}
// For all other values, assign
// ans[i + val] to val if the
// i + val < ans.length
else if (i + val < ans.length && ans[i + val] === 0) {
ans[val + i] = val;
// Recursively call for
// next index to check if
// solution can be found
var found = constructArray(i + 1, N);
// If solution is found then
// return true
if (found) return true;
// BackTracking step
ans[i + val] = 0;
}
// BackTracking step
ans[i] = 0;
var index = visited.indexOf(val);
if (index !== -1) {
visited.splice(index, 1);
}
}
}
// In all other cases, return false
return false;
}
// Driver Code
var N = 4;
ans = new Array(2 * N - 1).fill(0);
visited = [];
// Function Call
constructArray(0, N);
// Print the resultant array
for (const X of ans) {
document.write(X + " ");
}
</script>
Producción:
4 2 3 2 4 3 1
Complejidad temporal: O(N!)
Espacio auxiliar: O(N)