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

**Examples:**

Example 1:Input:N = 5, r = 3Output:60Explanation: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