Cuente el número de formas de organizar los primeros N números naturales en una línea de modo que el número más a la izquierda sea siempre 1 y no haya dos números consecutivos que tengan una diferencia absoluta mayor que 2 .
Ejemplos:
Entrada: N = 4
Salida: 4
Los únicos arreglos posibles son (1, 2, 3, 4),
(1, 2, 4, 3), (1, 3, 4, 2) y (1, 3, 2, 4).Entrada: N = 6
Salida: 9
Enfoque ingenuo: genere todas las permutaciones y cuente cuántas de ellas satisfacen las condiciones dadas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the count
// of required arrangements
int countWays(int n)
{
// Create a vector
vector<int> a;
int i = 1;
// Store numbers from 1 to n
while (i <= n)
a.push_back(i++);
// To store the count of ways
int ways = 0;
// Generate all the permutations
// using next_permutation in STL
do {
// Initialize flag to true if first
// element is 1 else false
bool flag = (a[0] == 1);
// Checking if the current permutation
// satisfies the given conditions
for (int i = 1; i < n; i++) {
// If the current permutation is invalid
// then set the flag to false
if (abs(a[i] - a[i - 1]) > 2)
flag = 0;
}
// If valid arrangement
if (flag)
ways++;
// Generate the next permutation
} while (next_permutation(a.begin(), a.end()));
return ways;
}
// Driver code
int main()
{
int n = 6;
cout << countWays(n);
return 0;
}
Java
// Java implementation of the
// above approach
import java.util.*;
class GFG{
// Function to return the count
// of required arrangements
static int countWays(int n)
{
// Create a vector
Vector<Integer> a =
new Vector<>();
int i = 1;
// Store numbers from
// 1 to n
while (i <= n)
a.add(i++);
// To store the count
// of ways
int ways = 0;
// Generate all the permutations
// using next_permutation in STL
do
{
// Initialize flag to true
// if first element is 1
// else false
boolean flag = (a.get(0) == 1);
// Checking if the current
// permutation satisfies the
// given conditions
for (int j = 1; j < n; j++)
{
// If the current permutation
// is invalid then set the
// flag to false
if (Math.abs(a.get(j) -
a.get(j - 1)) > 2)
flag = false;
}
// If valid arrangement
if (flag)
ways++;
// Generate the next permutation
} while (next_permutation(a));
return ways;
}
static boolean next_permutation(Vector<Integer> p)
{
for (int a = p.size() - 2;
a >= 0; --a)
if (p.get(a) < p.get(a + 1))
for (int b = p.size() - 1;; --b)
if (p.get(b) > p.get(a))
{
int t = p.get(a);
p.set(a, p.get(b));
p.set(b, t);
for (++a, b = p.size() - 1;
a < b; ++a, --b)
{
t = p.get(a);
p.set(a, p.get(b));
p.set(b, t);
}
return true;
}
return false;
}
// Driver code
public static void main(String[] args)
{
int n = 6;
System.out.print(countWays(n));
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 implementation of the approach from itertools import permutations # Function to return the count # of required arrangements def countWays(n): # Create a vector a = [] i = 1 # Store numbers from 1 to n while (i <= n): a.append(i) i += 1 # To store the count of ways ways = 0 # Generate the all permutation for per in list(permutations(a)): # Initialize flag to true if first # element is 1 else false flag = 1 if (per[0] == 1) else 0 # Checking if the current permutation # satisfies the given conditions for i in range(1, n): # If the current permutation is invalid # then set the flag to false if (abs(per[i] - per[i - 1]) > 2): flag = 0 # If valid arrangement if (flag): ways += 1 return ways # Driver code n = 6 print(countWays(n)) # This code is contributed by shivanisinghss2110
C#
// C# implementation of the
// above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to return the count
// of required arrangements
static int countWays(int n)
{
// Create a vector
List<int> a =
new List<int>();
int i = 1;
// Store numbers from
// 1 to n
while (i <= n)
a.Add(i++);
// To store the count
// of ways
int ways = 0;
// Generate all the
// permutations using
// next_permutation in STL
do
{
// Initialize flag to true
// if first element is 1
// else false
bool flag = (a[0] == 1);
// Checking if the current
// permutation satisfies the
// given conditions
for (int j = 1; j < n; j++)
{
// If the current permutation
// is invalid then set the
// flag to false
if (Math.Abs(a[j] -
a[j - 1]) > 2)
flag = false;
}
// If valid arrangement
if (flag)
ways++;
// Generate the next
// permutation
} while (next_permutation(a));
return ways;
}
static bool next_permutation(List<int> p)
{
for (int a = p.Count - 2;
a >= 0; --a)
if (p[a] < p[a + 1])
for (int b = p.Count - 1;; --b)
if (p[b] > p[a])
{
int t = p[a];
p[a] = p[b];
p[b] = t;
for (++a, b = p.Count - 1;
a < b; ++a, --b)
{
t = p[a];
p[a] = p[b];
p[b] = t;
}
return true;
}
return false;
}
// Driver code
public static void Main(String[] args)
{
int n = 6;
Console.Write(countWays(n));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation of the
// above approach
// Function to return the count
// of required arrangements
function countWays(n)
{
// Create a vector
let a =[];
let i = 1;
// Store numbers from
// 1 to n
while (i <= n)
a.push(i++);
// To store the count
// of ways
let ways = 0;
// Generate all the permutations
// using next_permutation in STL
do
{
// Initialize flag to true
// if first element is 1
// else false
let flag = (a[0] == 1);
// Checking if the current
// permutation satisfies the
// given conditions
for (let j = 1; j < n; j++)
{
// If the current permutation
// is invalid then set the
// flag to false
if (Math.abs(a[j] -
a[j - 1]) > 2)
flag = false;
}
// If valid arrangement
if (flag)
ways++;
// Generate the next permutation
} while (next_permutation(a));
return ways;
}
function next_permutation(p)
{
for (let a = p.length - 2;a >= 0; --a)
{if (p[a] < p[a + 1])
{for (let b = p.length - 1;; --b)
{if (p[b] > p[a])
{
let t = p[a];
p[a] = p[b];
p[b] = t;
for (++a, b = p.length - 1;
a < b; ++a, --b)
{
t = p[a];
p[a] = p[b];
p[b] = t;
}
return true;
}
}
}
}
return false;
}
// Driver code
let n = 6;
document.write(countWays(n));
// This code is contributed by patel2127
</script>
Producción:
9
Enfoque eficiente: este problema se puede resolver mediante programación dinámica .
Un mejor enfoque lineal para este problema se basa en la siguiente observación. Busque la posición de 2. Sea a[i] el número de formas para n = i. Hay tres casos:
- 12_____ – “2” en la segunda posición.
- 1*2____ – “2” en la tercera posición.
1**2___ – “2” en la cuarta posición es imposible porque la única forma posible es (1342), que es igual al caso 3.
1***2__ – “2” en la quinta posición es imposible porque se debe seguir 1 por 3 , 3 por 5 y 2 necesita 4 antes de que se convierta en 13542 , nuevamente como el caso 3. - 1_(i – 2)terms___2 – “2” en la última posición (1357642 y similares)
Para cada caso, las siguientes son las subtareas:
Sumar 1 a cada término de a[i – 1], es decir (1__(i – 1) términos__).
En cuanto a 1_2_____ solo puede haber un 1324___(i – 4) términos____ es decir a[i – 3].
Por lo tanto, la relación de recurrencia será,
a[i] = a[i – 1] + a[i – 3] + 1
Y los casos base serán:
a[0] = 0
a[1] = 1
a[2] = 1
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the count
// of required arrangements
int countWays(int n)
{
// Create the dp array
int dp[n + 1];
// Initialize the base cases
// as explained above
dp[0] = 0;
dp[1] = 1;
// (12) as the only possibility
dp[2] = 1;
// Generate answer for greater values
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 3] + 1;
}
// dp[n] contains the desired answer
return dp[n];
}
// Driver code
int main()
{
int n = 6;
cout << countWays(n);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the count
// of required arrangements
static int countWays(int n)
{
// Create the dp array
int []dp = new int[n + 1];
// Initialize the base cases
// as explained above
dp[0] = 0;
dp[1] = 1;
// (12) as the only possibility
dp[2] = 1;
// Generate answer for greater values
for (int i = 3; i <= n; i++)
{
dp[i] = dp[i - 1] + dp[i - 3] + 1;
}
// dp[n] contains the desired answer
return dp[n];
}
// Driver code
public static void main(String args[])
{
int n = 6;
System.out.println(countWays(n));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python implementation of the approach # Function to return the count # of required arrangements def countWays(n): # Create the dp array dp = [0 for i in range(n + 1)] # Initialize the base cases # as explained above dp[0] = 0 dp[1] = 1 # (12) as the only possibility dp[2] = 1 # Generate answer for greater values for i in range(3, n + 1): dp[i] = dp[i - 1] + dp[i - 3] + 1 # dp[n] contains the desired answer return dp[n] # Driver code n = 6 print(countWays(n)) # This code is contributed by Mohit Kumar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the count
// of required arrangements
static int countWays(int n)
{
// Create the dp array
int []dp = new int[n + 1];
// Initialize the base cases
// as explained above
dp[0] = 0;
dp[1] = 1;
// (12) as the only possibility
dp[2] = 1;
// Generate answer for greater values
for (int i = 3; i <= n; i++)
{
dp[i] = dp[i - 1] + dp[i - 3] + 1;
}
// dp[n] contains the desired answer
return dp[n];
}
// Driver code
public static void Main()
{
int n = 6;
Console.WriteLine(countWays(n));
}
}
// This code is contributed by Code@Mech.
Javascript
<script>
// Function to return the count
// of required arrangements
function countWays( n)
{
// Create the dp array
let dp = new Array (n + 1);
// Initialize the base cases
// as explained above
dp[0] = 0;
dp[1] = 1;
// (12) as the only possibility
dp[2] = 1;
// Generate answer for greater values
for (let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 3] + 1;
}
// dp[n] contains the desired answer
return dp[n];
}
// Driver code
let n = 6;
document.write(countWays(n));
// This code is contributed by shivanisinghss2110
</script>
Producción:
9
Complejidad de tiempo : O(N)
Complejidad de espacio: O(N)
Publicación traducida automáticamente
Artículo escrito por mayank77dh9 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA