Given the number N which represents the number of students, the task is to calculate all possible ways to rank them according to their CGPA/marks, considering that two or more students can have the same rank. Since the answer can be large, perform the modulo with 109 + 7.
Examples:
Input: N = 1
Output: 1
Explanation:
There is only one way to rank a student, irrespective of his marks.Input: N = 2
Output: 3
Explanation:
First way : if A and B student Got same marks, then Let say A has got higher rank than B .
Second Way : if A and B student Got same marks, then Let say B has got higher rank than A .
Third way: If both got different, Then the person got higher mark , will get higher rank.
Approach: The idea for this problem is to use the Bell Numbers.
- A bell number is a number that counts the possible partitions of a set. Therefore, an N-th bell number is a number of non-empty subsets a set of size N can be partitioned into.
- For example, let’s consider the set {1, 2, 3} for N = 3. The bell number corresponding to N = 3 is 5. This signifies that the given set can be partitioned into the following 5 non-empty subsets:
{{1}, {2}, {3}}
{{1, 2}, {3}}
{{1, 3}, {2}}
{{2, 3}, {1}}
{{1, 2, 3}}
- Clearly, the above bell numbers signify all the possible ranks. However, they do not calculate the permutations of the subset.
- Therefore, by multiplying every subset with K!, where K denotes the size of the respective subset, we get all the possible arrangements.
- As the same subproblems can be repeated, we can store the values of each subproblem in a data structure to optimize the complexity.
Implementation:
C++
// C++ program to calculate the number// of ways to give ranks for N// students such that same ranks// are possible#include <bits/stdc++.h>using namespace std;const int mod = 1e9 + 7;// Initializing a table in order to// store the bell trianglevector<vector<int> > dp;// Function to calculate the K-th// bell numberint f(int n, int k){ // If we have already calculated // the bell numbers until the // required N if (n < k) return 0; // Base case if (n == k) return 1; // First Bell Number if (k == 1) return 1; // If the value of the bell // triangle has already been // calculated if (dp[n][k] != -1) return dp[n][k]; // Fill the defined dp table return dp[n][k] = ((k * f(n - 1, k)) % mod + (f(n - 1, k - 1)) % mod) % mod;}// Function to return the number// of ways to give ranks for N// students such that same ranks// are possiblelong operation(int n){ // Resizing the dp table for the // given value of n dp.resize(n + 1, vector<int>(n + 1, -1)); // Variables to store the answer // and the factorial value long ans = 0, fac = 1; // Iterating till N for (int k = 1; k <= n; k++) { // Simultaneously calculate the k! fac *= k; // Computing the K-th bell number // and multiplying it with K! ans = (ans + (fac * f(n, k)) % mod) % mod; } return ans;}// Driver codeint main(){ int n = 5; cout << operation(n) << endl; return 0;} |
Java
// Java program to calculate the number// of ways to give ranks for N// students such that same ranks// are possibleimport java.util.*;class GFG{static int mod = (int)(1e9 + 7);// Initializing a table in order to// store the bell trianglestatic int [][]dp;// Function to calculate the K-th// bell numberstatic int f(int n, int k){ // If we have already calculated // the bell numbers until the // required N if (n < k) return 0; // Base case if (n == k) return 1; // First Bell Number if (k == 1) return 1; // If the value of the bell // triangle has already been // calculated if (dp[n][k] != -1) return dp[n][k]; // Fill the defined dp table return dp[n][k] = ((k * f(n - 1, k)) % mod + (f(n - 1, k - 1)) % mod) % mod;}// Function to return the number// of ways to give ranks for N// students such that same ranks// are possiblestatic long operation(int n){ // Resizing the dp table for the // given value of n dp = new int[n + 1][n + 1]; for(int i = 0; i < n + 1; i++) { for(int j = 0; j < n + 1; j++) { dp[i][j] = -1; } } // Variables to store the answer // and the factorial value long ans = 0, fac = 1; // Iterating till N for(int k = 1; k <= n; k++) { // Simultaneously calculate the k! fac *= k; // Computing the K-th bell number // and multiplying it with K! ans = (ans + (fac * f(n, k)) % mod) % mod; } return ans;}// Driver codepublic static void main(String[] args){ int n = 5; System.out.print(operation(n) + "\n");}}// This code is contributed by amal kumar choubey |
Python3
# Python3 program to calculate the number# of ways to give ranks for N# students such that same ranks# are possiblemod = 1e9 + 7# Initializing a table in order to# store the bell triangledp = [[-1 for x in range(6)] for y in range(6)]# Function to calculate the K-th# bell numberdef f(n, k): # If we have already calculated # the bell numbers until the # required N if (n < k): return 0 # Base case if (n == k): return 1 # First Bell Number if (k == 1): return 1 # If the value of the bell # triangle has already been # calculated if (dp[n][k] != -1): return dp[n][k] # Fill the defined dp table dp[n][k] = ((((k * f(n - 1, k)) % mod + (f(n - 1, k - 1)) % mod) % mod)) return dp[n][k]# Function to return the number# of ways to give ranks for N# students such that same ranks# are possibledef operation(n): # Resizing the dp table for the # given value of n global dp # Variables to store the answer # and the factorial value ans = 0 fac = 1 # Iterating till N for k in range(1, n + 1): # Simultaneously calculate the k! fac *= k # Computing the K-th bell number # and multiplying it with K! ans = (ans + (fac * f(n, k)) % mod) % mod return ans# Driver codeif __name__ == "__main__": n = 5 print(int(operation(n)))# This code is contributed by ukasp |
C#
// C# program to calculate the number// of ways to give ranks for N// students such that same ranks// are possibleusing System;class GFG{static int mod = (int)(1e9 + 7);// Initializing a table in order to// store the bell trianglestatic int [,]dp;// Function to calculate the K-th// bell numberstatic int f(int n, int k){ // If we have already calculated // the bell numbers until the // required N if (n < k) return 0; // Base case if (n == k) return 1; // First Bell Number if (k == 1) return 1; // If the value of the bell // triangle has already been // calculated if (dp[n, k] != -1) return dp[n, k]; // Fill the defined dp table return dp[n, k] = ((k * f(n - 1, k)) % mod + (f(n - 1, k - 1)) % mod) % mod;}// Function to return the number// of ways to give ranks for N// students such that same ranks// are possiblestatic long operation(int n){ // Resizing the dp table for the // given value of n dp = new int[n + 1, n + 1]; for(int i = 0; i < n + 1; i++) { for(int j = 0; j < n + 1; j++) { dp[i, j] = -1; } } // Variables to store the answer // and the factorial value long ans = 0, fac = 1; // Iterating till N for(int k = 1; k <= n; k++) { // Simultaneously calculate the k! fac *= k; // Computing the K-th bell number // and multiplying it with K! ans = (ans + (fac * f(n, k)) % mod) % mod; } return ans;}// Driver codepublic static void Main(String[] args){ int n = 5; Console.Write(operation(n) + "\n");}}// This code is contributed by amal kumar choubey |
Javascript
<script>// Javascript program to calculate the number// of ways to give ranks for N// students such that same ranks// are possible var mod = parseInt( 1e9 + 7); // Initializing a table in order to // store the bell triangle var dp; // Function to calculate the K-th // bell number function f(n , k) { // If we have already calculated // the bell numbers until the // required N if (n < k) return 0; // Base case if (n == k) return 1; // First Bell Number if (k == 1) return 1; // If the value of the bell // triangle has already been // calculated if (dp[n][k] != -1) return dp[n][k]; // Fill the defined dp table return dp[n][k] = ((k * f(n - 1, k)) % mod + (f(n - 1, k - 1)) % mod) % mod; } // Function to return the number // of ways to give ranks for N // students such that same ranks // are possible function operation(n) { // Resizing the dp table for the // given value of n dp = Array(n + 1).fill().map(() =>Array(n + 1).fill(0)); for (i = 0; i < n + 1; i++) { for (j = 0; j < n + 1; j++) { dp[i][j] = -1; } } // Variables to store the answer // and the factorial value var ans = 0, fac = 1; // Iterating till N for (k = 1; k <= n; k++) { // Simultaneously calculate the k! fac *= k; // Computing the K-th bell number // and multiplying it with K! ans = (ans + (fac * f(n, k)) % mod) % mod; } return ans; } // Driver code var n = 5; document.write(operation(n) + "\n");// This code contributed by umadevi9616 </script> |
Output:
541
Time Complexity: O(N*N)
Auxiliary Space: O(N*N)
Efficient approach: Using DP Tabulation method ( Iterative approach )
The approach to solving this problem is the same but DP tabulation(bottom-up) method is better the Dp + memorization(top-down) because memorization method needs extra stack space of recursion calls.
Steps to solve this problem:
- Create a vector to store the solution of the subproblems.
- Initialize the table with base cases
- Fill up the table iteratively.
- Return the final solution
Implementation:
C++
#include <bits/stdc++.h>using namespace std;const int mod = 1e9 + 7;int operation(int n){ vector<vector<int> > dp(n + 1, vector<int>(n + 1)); // Initialize base cases for (int i = 0; i <= n; i++) { dp[i][0] = 0; dp[i][i] = 1; } // Fill the DP table in a bottom-up manner for (int i = 1; i <= n; i++) { for (int j = 1; j < i; j++) { dp[i][j] = (j * dp[i - 1][j] + dp[i - 1][j - 1]) % mod; } dp[i][i] = 1; } // Calculate the answer using the DP table long ans = 0, fac = 1; for (int k = 1; k <= n; k++) { fac *= k; ans = (ans + (fac * dp[n][k]) % mod) % mod; } return ans;}// Driver codeint main(){ int n = 5; // function call cout << operation(n) << endl; return 0;} |
Java
import java.util.*;public class Main { static final int mod = 1000000007; static int operation(int n) { int[][] dp = new int[n+1][n+1]; // Initialize base cases for (int i = 0; i <= n; i++) { dp[i][0] = 0; dp[i][i] = 1; } // Fill the DP table in a bottom-up manner for (int i = 1; i <= n; i++) { for (int j = 1; j < i; j++) { dp[i][j] = (j * dp[i-1][j] + dp[i-1][j-1]) % mod; } dp[i][i] = 1; } // Calculate the answer using the DP table long ans = 0, fac = 1; for (int k = 1; k <= n; k++) { fac *= k; ans = (ans + (fac * dp[n][k]) % mod) % mod; } return (int)ans; } // Driver code public static void main(String[] args) { int n = 5; // function call System.out.println(operation(n)); }} |
Python
mod = 10**9 + 7def operation(n): dp = [[0 for j in range(n+1)] for i in range(n+1)] # Initialize base cases for i in range(n+1): dp[i][0] = 0 dp[i][i] = 1 # Fill the DP table in a bottom-up manner for i in range(1, n+1): for j in range(1, i): dp[i][j] = (j * dp[i-1][j] + dp[i-1][j-1]) % mod dp[i][i] = 1 # Calculate the answer using the DP table ans, fac = 0, 1 for k in range(1, n+1): fac *= k ans = (ans + (fac * dp[n][k]) % mod) % mod return ans# Driver coden = 5print(operation(n)) |
C#
using System;using System.Collections.Generic;class Solution { static int mod = 1000000007; static int operation(int n) { // 2D array to store the DP values int[][] dp = new int[n + 1][]; // Initialize base cases for (int i = 0; i <= n; i++) { dp[i] = new int[n + 1]; dp[i][0] = 0; dp[i][i] = 1; } // Fill the DP table in a bottom-up manner for (int i = 1; i <= n; i++) { for (int j = 1; j < i; j++) { dp[i][j] = (j * dp[i - 1][j] + dp[i - 1][j - 1]) % mod; } dp[i][i] = 1; } // Calculate the answer using the DP table long ans = 0, fac = 1; for (int k = 1; k <= n; k++) { fac *= k; ans = (ans + (fac * dp[n][k]) % mod) % mod; } return (int)ans; } // Driver code static void Main(string[] args) { int n = 5; // Function call Console.WriteLine(operation(n)); }}// This code is contributed by user_dtewbxkn77n |
Javascript
const mod = 10**9 + 7;function operation(n) { let dp = Array.from(Array(n+1), () => new Array(n+1).fill(0)); // Initialize base cases for (let i = 0; i <= n; i++) { dp[i][0] = 0; dp[i][i] = 1; } // Fill the DP table in a bottom-up manner for (let i = 1; i <= n; i++) { for (let j = 1; j < i; j++) { dp[i][j] = (j * dp[i-1][j] + dp[i-1][j-1]) % mod; } dp[i][i] = 1; } // Calculate the answer using the DP table let ans = 0, fac = 1; for (let k = 1; k <= n; k++) { fac *= k; ans = (ans + (fac * dp[n][k]) % mod) % mod; } return ans;}// Driver codelet n = 5;console.log(operation(n)); |
Output
541
Time Complexity: O(N*N)
Auxiliary Space: O(N*N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
