Data Modelling & AI Data Structure & Algorithm

Count the number of ways to give ranks for N students such that same ranks are possible

21 June 2025

0

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 10⁹ + 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 triangle
vector<vector<int> > dp;
 
// Function to calculate the K-th
// bell number
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 possible
long 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 code
int 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 possible
import java.util.*;
 
class GFG{
 
static int mod = (int)(1e9 + 7);
 
// Initializing a table in order to
// store the bell triangle
static int [][]dp;
 
// Function to calculate the K-th
// bell number
static 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 possible
static 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 code
public 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 possible
mod = 1e9 + 7
 
# Initializing a table in order to
# store the bell triangle
dp = [[-1 for x in range(6)] 
          for y in range(6)]
 
# Function to calculate the K-th
# bell number
def 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 possible
def 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 code
if __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 possible
using System;
 
class GFG{
 
static int mod = (int)(1e9 + 7);
 
// Initializing a table in order to
// store the bell triangle
static int [,]dp;
 
// Function to calculate the K-th
// bell number
static 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 possible
static 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 code
public 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:

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 code
int 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 + 7
 
def 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 code
n = 5
print(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 code
let n = 5;
console.log(operation(n));

Output

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!

Count the number of ways to give ranks for N students such that same ranks are possible

C++

Java

Python3

C#

Javascript

C++

Java

Python

C#

Javascript

When Context Engineering Is Done Right, Hallucinations Can Be the Spark of AI Creativity

Getting Started with langgraph-up-react: A Practical LangGraph Template

LangChain vs LangGraph: A Developer’s Guide to Choosing Your AI Frameworks

LEAVE A REPLY Cancel reply

Most Popular

Google Maps has become my ultimate city guide, thanks to this simple strategy

Steam Pulls Game After Malware Steals Over $150,000 in Crypto by Husain Parvez

Instagram CEO wants to let you know that the app doesn’t eavesdrop on your conversations

Google Wallet’s fresh new look is finally available to all

EDITOR PICKS

Google Maps has become my ultimate city guide, thanks to this simple strategy

Steam Pulls Game After Malware Steals Over $150,000 in Crypto by Husain Parvez

Instagram CEO wants to let you know that the app doesn’t eavesdrop on your conversations

POPULAR POSTS

Google Maps has become my ultimate city guide, thanks to this simple strategy

Steam Pulls Game After Malware Steals Over $150,000 in Crypto by Husain Parvez

Instagram CEO wants to let you know that the app doesn’t eavesdrop on your conversations

POPULAR CATEGORY

ABOUT US

FOLLOW US