Permutations in Which N People Can Occupy R Seats

13
0

Given two integers N and R, representing the total number of people and the number of available seats, respectively. The task is to calculate the number of permutations in which these N people can occupy the R seats.

Since the answer can be very large, return the result modulo 10^9 + 7.

Example 1

Input: N = 5, R = 3

Output: 60

Explanation: The number of ways in which 5 people can occupy 3 seats is :-

P(5, 3) = 5! / (5 - 3)!

= 5! / 2!

= 120 / 2 = 60

Example 2

Input: N = 4, R = 2

Output: 12

Explanation: The number of ways in which 4 people can occupy 2 seats is :-

P(4, 2) = 4! / 2! = 24 / 2 = 12

Approach

The simplest idea is to calculate the number of choices available for each seat and multiply all the choices together. For the first seat, all N people are available. After selecting one person, only N - 1 people remain for the second seat. Similarly, the number of available choices keeps decreasing for every subsequent seat.

Since only R seats need to be occupied, exactly R terms need to be multiplied.

This gives the permutation formula:

P(N, R) = N × (N-1) × (N-2) × ... × (N-R+1)

There is no need to calculate the complete factorial because only the first R terms are required.

Algorithm

  • Initialize a result variable with 1 to store the final permutation count.

  • Iterate from 0 to R-1, representing each available seat.

  • For every iteration, multiply the result by the number of remaining people (N - i).

  • Apply modulo 10^9 + 7 after every multiplication to keep the result within the required range.

  • After completing all iterations, return the final result.

Dry Run

Permutations in which N people can occupy R seats

Permutations in which N people can occupy R seats

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function to calculate permutations of N people in R seats
long long permutations(int N, int R) {
// Modulo value
const long long MOD = 1e9 + 7;
// Initialize result
long long result = 1;
// Multiply choices for each seat
for (int i = 0; i < R; i++) {
// Multiply and take modulo
result = (result * (N - i)) % MOD;
}
// Return final result
return result;
}
};
// Driver Code Starts
int main() {
// Example input
int N = 5, R = 3;
// Create Solution object
Solution obj;
// Print result
cout << obj.permutations(N, R) << endl;
return 0;
}

Complexity Analysis

  • Time Complexity: O(R), where R represents the number of available seats. The loop executes exactly R times, with one multiplication and modulo operation in each iteration.

  • Space Complexity: O(1), as only a constant amount of extra space is used for storing the result, modulo value, and loop variable.

Interview follow-up Questions

The permutation result can become very large. Applying modulo after every multiplication keeps the intermediate result manageable and prevents integer overflow in languages with fixed-size numeric types.

MathsTCS NQT

Read Similar Blogs

Comments0