# 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