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
1to store the final permutation count.Iterate from
0toR-1, representing each available seat.For every iteration, multiply the result by the number of remaining people (
N - i).Apply modulo
10^9 + 7after 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
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 Startsint 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.
Be the first to add a comment.