- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

In the given problem, we are given a string consisting of 0’s and 1’s; we are required to find the total number of permutations such that the string starts with 1’s. As the answer can be a vast number, so we print as a mod with 1000000007.

Input : str ="10101001001" Output : 210 Input : str ="101110011" Output : 56

We will solve the given problem by applying some combinatorics and building up some formulas to solve this problem.

In the approach, we will calculate the number of 0's and 1's. Now let's suppose n is the number of 1's present in our string and m be the number of 0's present in our string and let L be the length of our given string, so the formula that we make to solve this problem is (L-1)!/ (n-1)! * m!.

#include <bits/stdc++.h> #define MOD 1000000007 // defining 1e9 + 7 as MOD using namespace std; long long fact(long long n) { if(n <= 1) return 1; return ((n % MOD) * (fact(n-1) % MOD)) % MOD; } int main() { string s = "101110011"; long long L = s.size(); // length of given string long long count_1 = 0, count_0 = 0; // keeping count of 1's and 0's for(auto x : s) { if(x == '1') count_1++; // frequency of 1's else count_0++; // frequency of 0's } if(count_1 == 0){ cout << "0\n"; // if string only consists of 0's so our answer will be 0 } else { long long factL = fact(L-1); // (L-1)! long long factn = fact(count_1 - 1); // (n-1)! long long factm = fact(count_0); // m! long long ans = factL / (factn * factm); // putting the formula cout << ans << "\n"; } return 0; }

56

The given program has a time complexity of O(N), where n is the length of our given string.

In this approach, we are counting the number of 1’s and 0’s present inside of our string now, we place one at the starting and now formulate all the possible permutations of 0’s and 1’s in the string of length L-1 so by formulating this we get the formula of (L-1)! / (n-1)! * m! Where (n-1)! Are the permutations of the remaining 1’s, and m! is the permutation of the 0’s.

In this article, we solve a problem to find the number of unique permutations starting with 1 of a Binary String by applying some combinatorics and making up a formula for it.

We also learned the C++ program for this problem and the complete approach ( Normal) by which we solved this problem. We can write the same program in other languages such as C, java, python, and other languages. We hope you find this article helpful.

- Related Questions & Answers
- C++ Program to Find the Number of Permutations of a Given String
- Find the Number of 1 Bits in a large Binary Number in C++
- C++ Permutations of a Given String Using STL
- Find the Number of Substrings of a String using C++
- Creating all possible unique permutations of a string in JavaScript
- All permutations of a string using iteration?
- Find the Number of Unique Pairs in an Array using C++
- Find the index of the first unique character in a given string using C++
- Number of flips to make binary string alternate - Set 1 in C++
- Count of cyclic permutations having XOR with other binary string as 0 in C++
- Check if a binary string contains all permutations of length k in C++
- C++ Program to Find the Number of occurrences of a given Number using Binary Search approach
- Find the Number of Unique Triplets Whose XOR is Zero using C++
- C/C++ Program to find the Product of unique prime factors of a number?
- Program to find longest consecutive run of 1 in binary form of a number in C++

Advertisements