Count even length strings from N even and M odd length strings

Updated

Given an integer N, denoting strings of even length and an integer M, denoting strings of odd length. The task is to count total strings whose length is even after concatenation of any number of strings from the given lengths. The strings should not be divided, that is, either the whole string is chosen or it is not chosen.  Strings must be considered only once and their permutations are not counted.

Examples :

Input : N = 2, M = 1
Output : 3
Explanation :
As N = 2, there will be two string with even length.
Suppose the string are - "ab" and "cd"
M = 1.
There is 1 string with odd length.
Let the string be "e".
Total possible even length strings that can be formed are-
1.
Only consider the string "ab".
2.
Only consider the string "cd".
3.
Consider both even length string- "ab" + "cd" = "abcd".
Note, we won't consider "cd" + "ab" as another string as essentitally,
they are similar.
Therefore, total ways to make strings of even length is 1 + 1 + 1 = 3

Input : N = 2, M = 2
Output : 7
Explanation :
There are two strings of even length - "ab" and "cd"
There are two strings of odd length - "def" and "ghijk"
Total ways to make a string of even length -
1.
Consider even strings individually.
Total ways = 2
2.
Consider both even strings- "ab" + "cd".
Total ways = 1
3.
Consider both odd string - "def" + "ghijk".
Total ways = 1
4.
Consider first even string + both odd strings - "ab" + "def" +
"ghijk".
Total ways = 1.
5.
Consider second even string + both odd strings - "cd" + "def" +
"ghijk".
Total ways = 1.
6.
Consider all even strings + all odd strings - "ab" + "cd" + "def" +
"ghijk".
Total ways = 1
Therefore, total ways = 2 + 1 + 1 + 1 + 1 + 1 = 7

Input : N = 5, M = 4
Output : 255

Approach :

Given N even strings and M odd strings.
Consider the below points-
1. To make an even string either take:
       a) Any of the even strings 
       b) Any of the even string and odd strings of multiple of 2
       c) Odd strings in multiple of 2
   Therefore, total ways to make an even length string =
   (NC0 + NC1 + NC2+...+ NCN)*(MC0 + MC2 + MC4 +.... + MC(M-1))

 The above equation can be written as-
 = 2N * 2M-1 -1
 = 2N+M-1 -1

Follow the below steps to solve the problem:

  • Calculate 2N+M-1 using modular exponentiation under mod M
  • Return the answer

Implementation :

// C++ program to implement
// the above approach

#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007

// Function to find the value
// of power(X, N) % M
long long power(long long x,
				long long N)
{
	// Stores the value
	// of (X ^ N) % MOD
	long long res = 1;

	// Calculate the value of
	// power(x, N) % MOD
	while (N > 0) {

		// If N is odd
		if (N & 1) {

			// Update res
			res = (res * x) % MOD;
		}

		// Update x
		x = (x * x) % MOD;

		// Update N
		N = N >> 1;
	}
	return res;
}

// Function to count of total even lengths 
long long findLen(long long N,
			long long M)
{

	// Stores power(2, N + M - 1)
	long long P_2 = power(2, N + M - 1);
    
	return P_2 -1;

}

// Driver code
int main()
{

	long long N = 5;
	long long M = 4;
	cout << findLen(N, M);
}

Output :

255

Time Complexity : O(log2N * log2M)
Auxiliary Space : O(1)

Comment
Next tutorial
Mithlesh Upadhyay Published 20 Nov 2026 · 3 min read

Mithlesh Upadhyay is a Computer Science and AI expert from Madhya Pradesh with strong academic background (BE in CSE and M.Tech in AI) and over six years of experience in technical content development. He has contributed tech articles, led teams, and worked in Full Stack Development and Data Science. He founded the w3colleges.org portal for learning resources.

Related tutorials