Number of ways such that only K bars are visible from the left

0 0 14 minutes read

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 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 visible 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;
}

Java

// Java program for above approach
import 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 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 visible 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 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 permutation
function 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 arrangement
function 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 left
function 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

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

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

Output

Time Complexity: O(2^N)
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 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>

Output

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 zambiatek!