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)