Permutations in which N people can occupy R seats

Problem Statement: Find permutations in which n people can occupy r seats in a classroom.

Examples:

Example 1:
Input: N = 5, r = 3
Output: 60
Explanation: To permute n people in r seats we have to find the value of n!/(n-r)!.The value of 5!/(5-3)! Is 60.

Example 2:
Input: N=6,r = 4.
Output: 360

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution 1:

Intuition: The permutation in which n people can occupy r seats is n!/(n-r)!.

Approach:

  • Maintain two variables num and den to store numerator and denominator.
  • We need to find n! and (n-r)!.
  • Traverse from 1 to n and multiple i by num to find n!.
  • Traverse from 1 to (n-r) and multiply i by den to find (n-r)!.
  • num/den is the final answer.

Code:

C++ Code

#include<bits/stdc++.h>
using namespace std;
int fact(int n) {
	int ans = 1;
	for (int i = 1; i <= n; i++) {
		ans *= i;
	}
	return ans;
}
int main() {
	int n = 6, r = 4;
	int num = fact(n);
	int den = fact(n - r);
	cout << num / den;
}

Output: 360

Time Complexity: O(n)+O(n).O(n) for calculating n! and O(n) for calculating (n-r)!

Space Complexity: O(1).

Java Code

public class Main {
  static int fact(int n) {
    int ans = 1;
    for (int i = 1; i <= n; i++) {
      ans *= i;
    }
    return ans;
  }
  public static void main(String args[]) {
    int n = 6, r = 4;
    int num = fact(n);
    int den = fact(n - r);
    System.out.print(num / den);
  }
}

Output: 360

Time Complexity: O(n)+O(n).O(n) for calculating n! and O(n) for calculating (n-r)!

Space Complexity: O(1).

Solution 2:Optimized

Intuition: n!/(n-r)! can also be written as n*(n-1)*(n-2)….(n-r+1).Using this we can calculate n!/(n-r)! in O(n) time complexity.

Approach:

  • Maintain a variable ans to store answer.
  • Now run a for loop from n to (n-r+1) and multiply i to ans.
  • Print ans.

Code:

C++ Code

#include<bits/stdc++.h>
using namespace std;
int main() {
	int n = 6, r = 4;
	int ans = 1;
	for (int i = n; i >= n - r + 1; i--) {
		ans *= i;
	}
	cout << ans;
}

Output: 360

Time Complexity: O(n),as we are running a for loop from n to (n-r+1) 

Space Complexity: O(1)

Java Code

public class Main {
  public static void main(String args[]) {
    int n = 6, r = 4;
    int ans = 1;
    for (int i = n; i >= n - r + 1; i--) {
      ans *= i;
    }
    System.out.print(ans);
  }
}

Output: 360

Time Complexity: O(n),as we are running a for loop from n to (n-r+1) 

Space Complexity: O(1)

Special thanks to Pranav Padawe for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article