Roy bought a new bike last Sunday. He needs
to decide the number plate number now.
Though he likes O's and 1's most out of
number system, he wants his number plate to
start with 1. Lets help him in finding out how
many unique permutations start with 1 when
he is given with N O's and M 1's.
The code is given below. Complete the missing
lines of code to execute the program. Try
printing the answer modulo (10^9+7).
long long fact(int n, int m)
Answers
Answer:
Number of unique permutations starting with 1 of a Binary String
Given a binary string composed of 0’s and 1’s. The task is to find the number of unique permutation of the string which starts with 1.
Note: Since the answer can be very large, print the answer under modulo 109 + 7.
Examples:
Input : str ="10101001001"
Output : 210
Input : str ="101110011"
Output : 56
Recommended: Please try your approach on {IDE} first, before moving on to the solution.
The idea is to first find the count of 1’s and the count of 0’s in the given string. Now let us consider that the string is of length
L and the string consists of at least one 1. Let the number of 1’s be
n and the number of 0’s be
m. Out of n number of 1’s we have to place one 1 at the beginning of the string so we have n-1 1’s left and m 0’s w have to permute these (n-1) 1’s and m 0’s in length (L-1) of the string.
Therefore, the number of permutation will be:
(L-1)! / ((n-1)!*(m)!)
Below is the implementation of the above idea:
// C++ program to find number of unique permutations
// of a binary string starting with 1
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000003
#define mod 1000000007
// Array to store factorial of i at
// i-th index
long long fact[MAX];
// Precompute factorials under modulo mod
// upto MAX
void factorial()
{
// factorial of 0 is 1
fact[0] = 1;
for (int i = 1; i < MAX; i++) {
fact[i] = (fact[i - 1] * i) % mod;
}
}
// Iterative Function to calculate (x^y)%p in O(log y)
long long power(long long x, long long y, long long p)
{
long long res = 1; // Initialize result
x = x % p; // Update x if it is more than or
// equal to p
while (y > 0) {
// If y is odd, multiply x with result
if (y & 1)
res = (res * x) % p;
// y must be even now
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return res;
}
// Function to find the modular inverse
long long inverse(int n)
{
return power(n, mod - 2, mod);
}
// Function to find the number of permutation
// starting with 1 of a binary string
int countPermutation(string s)
{
// Generate factorials upto MAX
factorial();
int length = s.length(), num1 = 0, num0;
long long count = 0;
// find number of 1's
for (int i = 0; i < length; i++) {
if (s[i] == '1')
num1++;
}
// number of 0's
num0 = length - num1;
// Find the number of permuattion of
// string starting with 1 using the formulae:
// (L-1)! / ((n-1)!*(m)!)
count = (fact[length - 1] *
inverse((fact[num1 - 1] *
fact[num0]) % mod)) % mod;
return count;
}
// Driver code
int main()
{
string str = "10101001001";
cout << countPermutation(str);
return 0;
Output:
210
Time Complexity: O(n), where n is the length of the string.
Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.
Here is the complete code to solve the problem:
Code:
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
long long fact(int n, int m) {
long long res = 1;
for (int i = 1; i <= m; i++) {
res = (res * (n+i)) % MOD;
}
return res;
}
int main() {
int n, m;
cin >> n >> m;
long long ans = fact(n-1, m);
cout << ans << endl;
return 0;
}
Explanation:
The problem asks to find the number of unique permutations of N O's and M 1's that start with 1. We can solve this problem by noticing that the first digit must be 1, and the remaining digits can be permuted in any order. So the number of unique permutations is the number of ways we can permute the remaining (N-1) O's and M 1's.
To find the number of ways to permute (N-1) O's and M 1's, we can use the formula for permutations with repetition. The formula is given by:
nPr = (n+r-1)! / (r! * (n-1)!)
where n is the number of objects to choose from, r is the number of objects to choose, and ! denotes the factorial function.
In this case, we have (N-1) O's and M 1's to choose from, and we need to choose M 1's. So the number of ways to permute (N-1) O's and M 1's is given by:
(N-1+M)! / (M! * (N-1)!)
We can simplify this expression to:
(N+M-1) * (N+M-2) * ... * (N+1) / M!
We can compute this expression using a loop, taking care to compute the product modulo (10^9+7) at each step. The final answer is the number of ways to permute (N-1) O's and M 1's, multiplied by 1 (since the first digit must be 1).
#SPJ3