Data Modelling & AI Data Structure & Algorithm

Count ways to place M objects in distinct partitions of N boxes

23 June 2025

0

Given two positive integers N and M, the task is to find the number of ways to place M distinct objects in partitions of even indexed boxes which are numbered [1, N] sequentially, and every i^th Box has i distinct partitions. Since the answer can be very large, print modulo 1000000007.

Examples:

Input: N = 2, M = 1
Output: 2
Explanation: Since, N = 2. There is only one even indexed box i.e box 2, having 2 partitions. Therefore, there are two positions to place an object. Therefore, number of ways = 2.

Input: N = 5, M = 2
Output: 32

Approach: Follow the steps below to solve the problem:

M objects are to be placed in even indexed box’s partitions. Let S be the total even indexed box’s partitions in N boxes.
The number of partitions is equal to the summation of all even numbers up to N. Therefore, Sum, S = X * (X + 1), where X = floor(N / 2).
Each object can occupy one of S different positions. Therefore, the total number of ways = S*S*S..(M times) = S^M.

Below is the implementation of the above approach:

C++

// C++ implementation of the
// above Approach
 
#include <bits/stdc++.h>
using namespace std;
 
const int MOD = 1000000007;
 
// Iterative Function to calculate
// (x^y)%p in O(log y)
int power(int x, unsigned int y, int p = MOD)
{
    // Initialize Result
    int res = 1;
 
    // Update x if x >= MOD
    // to avoid multiplication overflow
    x = x % p;
 
    while (y > 0) {
 
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * 1LL * x) % p;
 
        // multiplied by long long int,
        // to avoid overflow
        // because res * x <= 1e18, which is
        // out of bounds for integer
 
        // n must be even now
 
        // y = y/2
        y = y >> 1;
 
        // Change x to x^2
        x = (x * 1LL * x) % p;
    }
    return res;
}
 
// Utility function to find
// the Total Number of Ways
void totalWays(int N, int M)
{
    // Number of Even Indexed
    // Boxes
    int X = N / 2;
 
    // Number of partitions of
    // Even Indexed Boxes
    int S = (X * 1LL * (X + 1)) % MOD;
 
    // Number of ways to distribute
    // objects
    cout << power(S, M, MOD) << "\n";
}
 
// Driver Code
int main()
{
    // N = number of boxes
    // M = number of distinct objects
    int N = 5, M = 2;
 
    // Function call to
    // get Total Number of Ways
    totalWays(N, M);
 
    return 0;
}

Java

// Java implementation of the
// above Approach
import java.io.*;
class GFG
{
   
public static int MOD = 1000000007;
 
// Iterative Function to calculate
// (x^y)%p in O(log y)
static int power(int x, int y, int p)
{    
      p = MOD;
   
    // Initialize Result
    int res = 1;
 
    // Update x if x >= MOD
    // to avoid multiplication overflow
    x = x % p;
 
    while (y > 0) 
    {
 
        // If y is odd, multiply x with result
        if ((y & 1) != 0)
            res = (res * x) % p;
 
        // multiplied by long long int,
        // to avoid overflow
        // because res * x <= 1e18, which is
        // out of bounds for integer
 
        // n must be even now
 
        // y = y/2
        y = y >> 1;
 
        // Change x to x^2
        x = (x * x) % p;
    }
    return res;
}
 
// Utility function to find
// the Total Number of Ways
static void totalWays(int N, int M)
{
   
    // Number of Even Indexed
    // Boxes
    int X = N / 2;
 
    // Number of partitions of
    // Even Indexed Boxes
    int S = (X * (X + 1)) % MOD;
 
    // Number of ways to distribute
    // objects
    System.out.println(power(S, M, MOD));
}
 
// Driver Code
public static void main (String[] args) 
{
     
      // N = number of boxes
    // M = number of distinct objects
    int N = 5, M = 2;
 
    // Function call to
    // get Total Number of Ways
    totalWays(N, M);
}
}
 
// This code is contributed by Dharanendra L V

Python3

# Python3 implementation of the
# above Approach
MOD = 1000000007
 
# Iterative Function to calculate
# (x^y)%p in O(log y)
def power(x, y, p = MOD):
   
    # Initialize Result
    res = 1
 
    # Update x if x >= MOD
    # to avoid multiplication overflow
    x = x % p
    while (y > 0):
 
        # If y is odd, multiply x with result
        if (y & 1):
            res = (res * x) % p
 
        # multiplied by long long int,
        # to avoid overflow
        # because res * x <= 1e18, which is
        # out of bounds for integer
 
        # n must be even now
 
        # y = y/2
        y = y >> 1
 
        # Change x to x^2
        x = (x * x) % p
    return res
 
# Utility function to find
# the Total Number of Ways
def totalWays(N, M):
   
    # Number of Even Indexed
    # Boxes
    X = N // 2
 
    # Number of partitions of
    # Even Indexed Boxes
    S = (X * (X + 1)) % MOD
 
    # Number of ways to distribute
    # objects
    print (power(S, M, MOD))
 
# Driver Code
if __name__ == '__main__':
 
    # N = number of boxes
    # M = number of distinct objects
    N, M = 5, 2
 
    # Function call to
    # get Total Number of Ways
    totalWays(N, M)
 
# This code is contributed by mohit kumar 29.

C#

// C# implementation of the
// above Approach
 
using System;
 
public class GFG{
 
public static int MOD = 1000000007;
 
// Iterative Function to calculate
// (x^y)%p in O(log y)
static int power(int x, int y, int p)
{
       
      p = MOD;
   
    // Initialize Result
    int res = 1;
 
    // Update x if x >= MOD
    // to avoid multiplication overflow
    x = x % p;
 
    while (y > 0) {
 
        // If y is odd, multiply x with result
        if ((y & 1) != 0)
            res = (res * x) % p;
 
        // multiplied by long long int,
        // to avoid overflow
        // because res * x <= 1e18, which is
        // out of bounds for integer
 
        // n must be even now
 
        // y = y/2
        y = y >> 1;
 
        // Change x to x^2
        x = (x * x) % p;
    }
    return res;
}
 
// Utility function to find
// the Total Number of Ways
static void totalWays(int N, int M)
{
   
    // Number of Even Indexed
    // Boxes
    int X = N / 2;
 
    // Number of partitions of
    // Even Indexed Boxes
    int S = (X * (X + 1)) % MOD;
 
    // Number of ways to distribute
    // objects
    Console.WriteLine(power(S, M, MOD));
}
 
// Driver Code
static public void Main ()
{
 
    // N = number of boxes
    // M = number of distinct objects
    int N = 5, M = 2;
 
    // Function call to
    // get Total Number of Ways
    totalWays(N, M);
}
}
 
// This code is contributed by Dharanendra L V

Javascript

<script>
 
// Javascript implementation of the
// above Approach
 
var MOD = 1000000007;
 
// Iterative Function to calculate
// (x^y)%p in O(log y)
function power(x, y, p = MOD)
{
    // Initialize Result
    var res = 1;
 
    // Update x if x >= MOD
    // to avoid multiplication overflow
    x = x % p;
 
    while (y > 0) {
 
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * 1 * x) % p;
 
        // multiplied by long long int,
        // to avoid overflow
        // because res * x <= 1e18, which is
        // out of bounds for integer
 
        // n must be even now
 
        // y = y/2
        y = y >> 1;
 
        // Change x to x^2
        x = (x * 1 * x) % p;
    }
    return res;
}
 
// Utility function to find
// the Total Number of Ways
function totalWays(N, M)
{
    // Number of Even Indexed
    // Boxes
    var X = parseInt(N / 2);
 
    // Number of partitions of
    // Even Indexed Boxes
    var S = (X * 1 * (X + 1)) % MOD;
 
    // Number of ways to distribute
    // objects
    document.write( power(S, M, MOD) << "<br>");
}
 
// Driver Code
// N = number of boxes
// M = number of distinct objects
var N = 5, M = 2;
// Function call to
// get Total Number of Ways
totalWays(N, M);
 
</script>

Output:

Time Complexity: O(log M)
Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 ways to place M objects in distinct partitions of N boxes

C++

Java

Python3

C#

Javascript

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

How to Debug Slow Search Requests in Milvus

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

LEAVE A REPLY Cancel reply

Most Popular

UFS 5.0 is on the way, but most Android users probably won’t notice

Android’s backup settings are returning to their former glory

Google’s earthquake alerts may soon be shareable

NotebookLM just made working with Google Drive a lot easier

EDITOR PICKS

UFS 5.0 is on the way, but most Android users probably won’t notice

Android’s backup settings are returning to their former glory

Google’s earthquake alerts may soon be shareable

POPULAR POSTS

UFS 5.0 is on the way, but most Android users probably won’t notice

Android’s backup settings are returning to their former glory

Google’s earthquake alerts may soon be shareable

POPULAR CATEGORY

ABOUT US

FOLLOW US