Count ways to place M objects in distinct partitions of N boxes
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 ith 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) = SM.
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 Waysvoid 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 Codeint 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 Approachimport 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 Waysstatic 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 Codepublic 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 ApproachMOD = 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 Waysdef 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 Codeif __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 Approachusing 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 Waysstatic 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 Codestatic 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 Approachvar 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 Waysfunction 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 objectsvar N = 5, M = 2;// Function call to// get Total Number of WaystotalWays(N, M);</script> |
Output:
36
Time Complexity: O(log M)
Auxiliary Space: O(1)
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 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
