Given a number K, and N bars of height from 1 to N, the task is to find the number of ways to arrange the N bars such that only K bars are visible from the left.
Examples:
Input: N=4, K=3
Output:
6
Explanation: The 6 permutations where only 3 bars are visible from the left are:
- 1 2 4 3
- 1 3 2 4
- 1 3 4 2
- 2 1 3 4
- 2 3 1 4
- 2 3 4 1
The Underlined bars are not visible.
Input: N=5, K=2
Output:
50
Naive Approach: The naive approach would be to check all permutations of 1 to N and check whether the number of bars visible from the left is K or not.
Below is the implementation of the above approach:
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 arrangementint 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 visible from the leftint 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 codeint main(){ // Input int N = 5, K = 2; // Function call cout << KvisibleFromLeft(N, K) << endl; return 0;} |
Java
// Java program for above approachimport java.util.*;public class Solution { // 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; for (int 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 generate next permutation of array 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 int t = nums[startIndex]; nums[startIndex] = nums[endIndex]; nums[endIndex] = t; } // 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) { int t = nums[start]; nums[start] = nums[end]; nums[end] = t; } } // Function to calculate the number // of rearrangements where // K bars are visible 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 System.out.println(KvisibleFromLeft(N, K)); }}// This code is contributed by karandeep1234. |
Python3
# Python3 program for the above approach# Function to calculate the number# of bars that are visible from# the left for a particular arrangementdef 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 ansdef 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 visible from the leftdef 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 codeif __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 approachusing 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 permutation 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 visible 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. |
Javascript
function swap(nums, i, j) { let temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } function reverse(nums, start) { let i = start, j = nums.length - 1; while (i < j) { swap(nums, i, j); i++; j--; } } // function to find next greater permutationfunction nextPermutation(nums) { let i = nums.length - 2; while (i >= 0 && nums[i + 1] <= nums[i]) { i--; } let flag= false; if (i >= 0) { let j = nums.length - 1; while (nums[j] <= nums[i]) { j--; } swap(nums, i, j); flag = true; } reverse(nums,i+1); return flag; }// Function to calculate the number// of bars that are visible from// the left for a particular arrangementfunction noOfbarsVisibleFromLeft(v){ let last = 0, ans = 0; for (let i=0;i< v.length;i++) // If current element is greater// than the last greater element,// it is visible if (last < v[i]) { ans++; last = v[i]; } return ans;}// Function to calculate the number// of rearrangements where// K bars are visible from the leftfunction KvisibleFromLeft(N, K){ // Vector to store current permutation let v=[]; for (let i = 0; i < N; i++) v.push(i + 1); let ans = 0; // Check for all permutations do { // If current permutation meets// the conditions, increment answer if (noOfbarsVisibleFromLeft(v) == K) ans++; } while (nextPermutation(v)==true); return ans;}// Driver code // Input let N = 5, K = 2; // Function call console.log( KvisibleFromLeft(N, K) );// This code is contributed by garg28harsh. |
Output
50
Time Complexity: O(N!)
Auxiliary Space: O(N)
Efficient Approach: The efficient approach would be to use recursion. Follow the steps below to solve the problem:
- Create a recursive function KvisibleFromLeft() that takes N and K as input parameters and does the following:
- Base cases:
- If N is equal to K, there is one way to arrange the bars, which is in ascending order. So, return 1.
- If K==1, there are (N-1)! ways to arrange the bars, as the longest bar is placed in the first position and the remaining N-1 bars can be placed anywhere on the remaining N-1 positions. So, return (N-1)!.
- For the recursion, there are two cases:
- The smallest bar can be placed at the first position, then, among the remaining N-1 bars, only K-1 bars need to be visible. Thus, the answer would be the same as the number of ways to arrange N-1 bars such that K-1 bars are visible. This case, thus, recursively calls KvisibleFromLeft(N-1, K-1).
- The smallest bar can be placed at any of the N-1 positions, other than the first. This would hide the smallest bar, and thus, the answer would be the same as the number of ways to arrange N-1 bars such that K bars are visible. Thus, this case recursively calls (N-1)*KvisibleFromLeft(N-1,K).
- Base cases:
Below is the implementation of the above approach:
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 codeint main(){ // Input int N = 5, K = 2; // Function call cout << KvisibleFromLeft(N, K) << endl; return 0;} |
Java
// Java program for the above approachclass 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 codepublic 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 codeif __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 approachusing 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 codepublic 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// Inputlet N = 5, K = 2;// Function calldocument.write(KvisibleFromLeft(N, K) + "<br>");// This code is contributed by gfgking.</script> |
Output
50
Time Complexity: O(2N)
Auxiliary Space: O(1)
Efficient Approach: The above recursion can be memoized and thus, dynamic programming can be used as there are optimal substructures.
Below is the implementation of the above approach:
C++
// C++ implementation for the above approach#include <bits/stdc++.h>using namespace std;// dp arrayint 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 codeint 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 approachimport java.util.*;class GFG{// dp arraystatic 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 codepublic 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 arraydp = [[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]# InputN, K = 5, 2# Initialize dp arrayfor i in range(1005): for j in range(1005): dp[i][j] = -1# Function callprint( KvisibleFromLeft(N, K))# This code is contributed by divyeshrabadiya07. |
C#
// C# implementation for the above approachusing System;public class GFG{// dp arraystatic 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 codepublic 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 arraylet 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// Inputlet N = 5, K = 2;// Function calldocument.write(KvisibleFromLeft(N, K) + "<br>")// This code is contributed by _saurabh_jaiswal</script> |
Output
50
Time Complexity: O(NK)
Auxiliary Space: O(NK)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
