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.
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>
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>
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