Dado un número K , y N barras de altura de 1 a N , la tarea es encontrar el número de formas de organizar las N barras de modo que solo las K barras sean visibles desde la izquierda.
Ejemplos :
Entrada: N=4, K=3
Salida:
6
Explicación: Las 6 permutaciones donde solo se ven 3 barras desde la izquierda son:
- 1 2 4 3
- 1 3 2 4
- 1 3 4 2
- 2 1 3 4
- 2 3 1 4
- 2 3 4 1
Las barras subrayadas no son visibles.
Entrada: N=5, K=2
Salida:
50
Enfoque ingenuo : el enfoque ingenuo sería verificar todas las permutaciones de 1 a N y verificar si el número de barras visibles desde la izquierda es K o no.
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 calculate the number
// of bars that are visible from
// the left for a particular arrangement
int noOfbarsVisibleFromLeft(vector<int> v)
{
int last = 0, ans = 0;
for (auto u : v)
// If current element is greater
// than the last greater element,
// it is visible
if (last < u) {
ans++;
last = u;
}
return ans;
}
// Function to calculate the number
// of rearrangements where
// K bars are visiblef from the left
int KvisibleFromLeft(int N, int K)
{
// Vector to store current permutation
vector<int> v(N);
for (int i = 0; i < N; i++)
v[i] = i + 1;
int ans = 0;
// Check for all permutations
do {
// If current permutation meets
// the conditions, increment answer
if (noOfbarsVisibleFromLeft(v) == K)
ans++;
} while (next_permutation(v.begin(), v.end()));
return ans;
}
// Driver code
int main()
{
// Input
int N = 5, K = 2;
// Function call
cout << KvisibleFromLeft(N, K) << endl;
return 0;
}
Python3
# Python3 program for the above approach # Function to calculate the number # of bars that are visible from # the left for a particular arrangement def noOfbarsVisibleFromLeft(v): last = 0 ans = 0 for u in v: # If current element is greater # than the last greater element, # it is visible if (last < u): ans += 1 last = u return ans def nextPermutation(nums): i = len(nums) - 2 while i > -1: if nums[i] < nums[i + 1]: j = len(nums) - 1 while j > i: if nums[j] > nums[i]: break j -= 1 nums[i], nums[j] = nums[j], nums[i] break i -= 1 nums[i + 1:] = reversed(nums[i + 1:]) return nums # Function to calculate the number # of rearrangements where # K bars are visiblef from the left def KvisibleFromLeft(N, K): # Vector to store current permutation v = [0]*(N) for i in range(N): v[i] = i + 1 ans = 0 temp = list(v) # Check for all permutations while True: # If current permutation meets # the conditions, increment answer if (noOfbarsVisibleFromLeft(v) == K): ans += 1 v = nextPermutation(v) if v == temp: break return ans # Driver code if __name__ == '__main__': # Input N = 5 K = 2 # Function call print (KvisibleFromLeft(N, K)) # This code is contributed by mohit kumar 29.
C#
// C# program to implement above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to calculate the number
// of bars that are visible from
// the left for a particular arrangement
static int noOfbarsVisibleFromLeft(int[] v)
{
int last = 0, ans = 0;
foreach (var u in v){
// If current element is greater
// than the last greater element,
// it is visible
if (last < u) {
ans++;
last = u;
}
}
return ans;
}
// Function to generate next permuation of array
public static void NextPermutation(int[] nums) {
// Starting from the end, look for the first index that is not in descending order
var startIndex = nums.Length - 2;
while (startIndex >= 0) {
// Find first decreasing element
if (nums[startIndex] < nums[startIndex + 1]) {
break;
}
--startIndex;
}
if (startIndex >= 0) {
// Starting from the end, look for the first element greater than the start index
int endIndex = nums.Length - 1;
while (endIndex > startIndex) {
// Find first greater element
if (nums[endIndex] > nums[startIndex]) {
break;
}
--endIndex;
}
// Swap first and last elements
Swap(ref nums[startIndex], ref nums[endIndex]);
}
// Reverse the array
Reverse(nums, startIndex + 1);
}
static void Reverse(int[] nums, int startIndex) {
for (int start = startIndex, end = nums.Length - 1; start < end; ++start, --end) {
Swap(ref nums[start], ref nums[end]);
}
}
static void Swap(ref int a, ref int b) {
var tmp = a;
a = b;
b = tmp;
}
// Function to calculate the number
// of rearrangements where
// K bars are visiblef from the left
static int KvisibleFromLeft(int N, int K)
{
// Vector to store current permutation
int[] v = new int[N];
for (int i = 0 ; i < N ; i++){
v[i] = i + 1;
}
int ans = 0;
int count = 1;
for(int i = 1 ; i <= N ; i++){
count *= i;
}
// Check for all permutations
for(int i = 0 ; i < count ; i++){
if (noOfbarsVisibleFromLeft(v) == K){
ans++;
}
NextPermutation(v);
}
return ans;
}
// Driver Code
public static void Main(string[] args){
// Input
int N = 5, K = 2;
// Function call
Console.Write(KvisibleFromLeft(N, K) + "\n");
}
}
// This code is contributed by subhamgoyal2014.
Producción
50
Complejidad temporal: O(N!)
Espacio auxiliar: O(N)
Enfoque eficiente: el enfoque eficiente sería utilizar la recursividad . Siga los pasos a continuación para resolver el problema:
- Cree una función recursiva KvisibleFromLeft() que tome N y K como parámetros de entrada y haga lo siguiente:
- Casos base:
- Si N es igual a K , hay una forma de ordenar las barras, que es en orden ascendente. Entonces, devuelve 1 .
- Si K==1 , hay (N-1)! formas de organizar las barras, ya que la barra más larga se coloca en la primera posición y las barras N-1 restantes se pueden colocar en cualquier lugar de las posiciones N-1 restantes . Entonces, ¡regresa (N-1)! .
- Para la recursividad, hay dos casos:
- La barra más pequeña se puede colocar en la primera posición, luego, entre las barras N-1 restantes , solo las barras K-1 deben ser visibles. Por lo tanto, la respuesta sería la misma que la cantidad de formas de organizar las barras N-1 de manera que las barras K-1 sean visibles. Este caso, por lo tanto, llama recursivamente a KvisibleFromLeft(N-1, K-1) .
- La barra más pequeña se puede colocar en cualquiera de las posiciones N-1 , excepto en la primera. Esto ocultaría la barra más pequeña y, por lo tanto, la respuesta sería la misma que la cantidad de formas de organizar N-1 barras de modo que las K barras sean visibles. Por lo tanto, este caso llama recursivamente a (N-1)*KvisibleFromLeft(N-1,K).
- Casos base:
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the number of permutations of
// N, where only K bars are visible from the left.
int KvisibleFromLeft(int N, int K)
{
// Only ascending order is possible
if (N == K)
return 1;
// N is placed at the first position
// The nest N-1 are arranged in (N-1)! ways
if (K == 1) {
int ans = 1;
for (int i = 1; i < N; i++)
ans *= i;
return ans;
}
// Recursing
return KvisibleFromLeft(N - 1, K - 1)
+ (N - 1) * KvisibleFromLeft(N - 1, K);
}
// Driver code
int main()
{
// Input
int N = 5, K = 2;
// Function call
cout << KvisibleFromLeft(N, K) << endl;
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function to calculate the number of
// permutations of N, where only K bars
// are visible from the left.
static int KvisibleFromLeft(int N, int K)
{
// Only ascending order is possible
if (N == K)
return 1;
// N is placed at the first position
// The nest N-1 are arranged in (N-1)! ways
if (K == 1)
{
int ans = 1;
for(int i = 1; i < N; i++)
ans *= i;
return ans;
}
// Recursing
return KvisibleFromLeft(N - 1, K - 1) +
(N - 1) * KvisibleFromLeft(N - 1, K);
}
// Driver code
public static void main(String[] args)
{
// Input
int N = 5, K = 2;
// Function call
System.out.println(KvisibleFromLeft(N, K));
}
}
// This code is contributed by abhinavjain194
Python3
# Python 3 implementation for the above approach # Function to calculate the number of permutations of # N, where only K bars are visible from the left. def KvisibleFromLeft(N, K): # Only ascending order is possible if (N == K): return 1 # N is placed at the first position # The nest N-1 are arranged in (N-1)! ways if (K == 1): ans = 1 for i in range(1, N, 1): ans *= i return ans # Recursing return KvisibleFromLeft(N - 1, K - 1) + (N - 1) * KvisibleFromLeft(N - 1, K) # Driver code if __name__ == '__main__': # Input N = 5 K = 2 # Function call print(KvisibleFromLeft(N, K)) # This code is contributed by ipg2016107.
C#
// C# program for the above approach
using System;
class GFG
{
// Function to calculate the number of
// permutations of N, where only K bars
// are visible from the left.
static int KvisibleFromLeft(int N, int K)
{
// Only ascending order is possible
if (N == K)
return 1;
// N is placed at the first position
// The nest N-1 are arranged in (N-1)! ways
if (K == 1)
{
int ans = 1;
for(int i = 1; i < N; i++)
ans *= i;
return ans;
}
// Recursing
return KvisibleFromLeft(N - 1, K - 1) +
(N - 1) * KvisibleFromLeft(N - 1, K);
}
// Driver code
public static void Main(String[] args)
{
// Input
int N = 5, K = 2;
// Function call
Console.Write(KvisibleFromLeft(N, K));
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// Javascript implementation for the above approach
// Function to calculate the number of permutations of
// N, where only K bars are visible from the left.
function KvisibleFromLeft(N, K) {
// Only ascending order is possible
if (N == K)
return 1;
// N is placed at the first position
// The nest N-1 are arranged in (N-1)! ways
if (K == 1) {
let ans = 1;
for (let i = 1; i < N; i++)
ans *= i;
return ans;
}
// Recursing
return KvisibleFromLeft(N - 1, K - 1)
+ (N - 1) * KvisibleFromLeft(N - 1, K);
}
// Driver code
// Input
let N = 5, K = 2;
// Function call
document.write(KvisibleFromLeft(N, K) + "<br>");
// This code is contributed by gfgking.
</script>
Producción
50
Complejidad temporal: O(2 N )
Espacio auxiliar: O(1)
Enfoque eficiente: la recursión anterior se puede memorizar y, por lo tanto, se puede usar la programación dinámica ya que hay subestructuras óptimas .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
// dp array
int dp[1005][1005];
// Function to calculate the number
// of permutations of N, where
// only K bars are visible from the left.
int KvisibleFromLeft(int N, int K)
{
// If subproblem has already
// been calculated, return
if (dp[N][K] != -1)
return dp[N][K];
// Only ascending order is possible
if (N == K)
return dp[N][K] = 1;
// N is placed at the first position
// The nest N-1 are arranged in (N-1)! ways
if (K == 1) {
int ans = 1;
for (int i = 1; i < N; i++)
ans *= i;
return dp[N][K] = ans;
}
// Recursing
return dp[N][K]
= KvisibleFromLeft(N - 1, K - 1)
+ (N - 1) * KvisibleFromLeft(N - 1, K);
}
// Driver code
int main()
{
// Input
int N = 5, K = 2;
// Initialize dp array
memset(dp, -1, sizeof(dp));
// Function call
cout << KvisibleFromLeft(N, K) << endl;
return 0;
}
Java
// Java implementation for the above approach
import java.util.*;
class GFG{
// dp array
static int [][]dp = new int[1005][1005];
// Function to calculate the number
// of permutations of N, where
// only K bars are visible from the left.
static int KvisibleFromLeft(int N, int K)
{
// If subproblem has already
// been calculated, return
if (dp[N][K] != -1)
return dp[N][K];
// Only ascending order is possible
if (N == K)
return dp[N][K] = 1;
// N is placed at the first position
// The nest N-1 are arranged in (N-1)! ways
if (K == 1) {
int ans = 1;
for (int i = 1; i < N; i++)
ans *= i;
return dp[N][K] = ans;
}
// Recursing
return dp[N][K]
= KvisibleFromLeft(N - 1, K - 1)
+ (N - 1) * KvisibleFromLeft(N - 1, K);
}
// Driver code
public static void main(String[] args)
{
// Input
int N = 5, K = 2;
// Initialize dp array
for(int i = 0; i < 1005; i++)
{
for (int j = 0; j < 1005; j++)
{
dp[i][j] = -1;
}
}
// Function call
System.out.print( KvisibleFromLeft(N, K));
}
}
// This code is contributed by shivanisinghss2110
Python3
# Python3 implementation for the above approach # dp array dp = [[0 for i in range(1005)] for j in range(1005)] # Function to calculate the number # of permutations of N, where # only K bars are visible from the left. def KvisibleFromLeft(N, K): # If subproblem has already # been calculated, return if (dp[N][K] != -1): return dp[N][K] # Only ascending order is possible if (N == K): dp[N][K] = 1 return dp[N][K] # N is placed at the first position # The nest N-1 are arranged in (N-1)! ways if (K == 1): ans = 1 for i in range(1, N): ans *= i dp[N][K] = ans return dp[N][K] # Recursing dp[N][K] = KvisibleFromLeft(N - 1, K - 1) + (N - 1) * KvisibleFromLeft(N - 1, K) return dp[N][K] # Input N, K = 5, 2 # Initialize dp array for i in range(1005): for j in range(1005): dp[i][j] = -1 # Function call print( KvisibleFromLeft(N, K)) # This code is contributed by divyeshrabadiya07.
C#
// C# implementation for the above approach
using System;
public class GFG{
// dp array
static int [,]dp = new int[1005, 1005];
// Function to calculate the number
// of permutations of N, where
// only K bars are visible from the left.
static int KvisibleFromLeft(int N, int K)
{
// If subproblem has already
// been calculated, return
if (dp[N ,K] != -1)
return dp[N,K];
// Only ascending order is possible
if (N == K)
return dp[N,K] = 1;
// N is placed at the first position
// The nest N-1 are arranged in (N-1)! ways
if (K == 1) {
int ans = 1;
for (int i = 1; i < N; i++)
ans *= i;
return dp[N,K] = ans;
}
// Recursing
return dp[N,K]
= KvisibleFromLeft(N - 1, K - 1)
+ (N - 1) * KvisibleFromLeft(N - 1, K);
}
// Driver code
public static void Main(String[] args)
{
// Input
int N = 5, K = 2;
// Initialize dp array
for(int i = 0; i < 1005; i++)
{
for (int j = 0; j < 1005; j++)
{
dp[i, j] = -1;
}
}
// Function call
Console.Write( KvisibleFromLeft(N, K));
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// Javascript implementation for
// the above approach
// dp array
let dp = new Array(1005).fill(0).map(
() => new Array(1005).fill(-1));
// Function to calculate the number
// of permutations of N, where
// only K bars are visible from the left.
function KvisibleFromLeft(N, K)
{
// If subproblem has already
// been calculated, return
if (dp[N][K] != -1)
return dp[N][K];
// Only ascending order is possible
if (N == K)
return dp[N][K] = 1;
// N is placed at the first position
// The nest N-1 are arranged in (N-1)! ways
if (K == 1)
{
let ans = 1;
for(let i = 1; i < N; i++)
ans *= i;
return dp[N][K] = ans;
}
// Recursing
return dp[N][K] = KvisibleFromLeft(N - 1, K - 1) +
(N - 1) * KvisibleFromLeft(N - 1, K);
}
// Driver code
// Input
let N = 5, K = 2;
// Function call
document.write(KvisibleFromLeft(N, K) + "<br>")
// This code is contributed by _saurabh_jaiswal
</script>
Producción
50
Complejidad temporal: O(NK)
Espacio auxiliar: O(NK)
Publicación traducida automáticamente
Artículo escrito por sohailahmed46khan786 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA