Count of N digit numbers not having given prefixes
source link: https://www.geeksforgeeks.org/count-of-n-digit-numbers-not-having-given-prefixes/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Count of N digit numbers not having given prefixes
- Last Updated : 24 Nov, 2021
Given an integer N and a vector of strings prefixes[], the task is to calculate the total possible strings of length N from characters ‘0’ to ‘9’. such that the given prefixes cannot be used in any of the strings.
Examples:
Input: N = 3, prefixes = {“42”}
Output: 990
Explanation: All string except{“420”, “421”, “422”, “423”, “424”, “425”, “426”, “427”, “428”, “429”} are valid.Input: N = 5, prefixes[]= { “0”, “1”, “911” }
Output: 79900
Approach: The total possible strings with length are (10^N) as for each place in a string there are 10 choices of the character. Instead of calculating total good strings, subtract total bad strings from total strings. Before iterating over the prefixesmerge prefixes with the same starting character as the bigger length prefix might lead to subtraction of some repetitions. Follow the steps below to solve the problem:
- Initialize the variable total as 10N.
- Initialize a map<int, vector<string>> mp[].
- Iterate over the range [0, M) using the variable i and perform the following tasks:
- Push the value of prefixes[i] in the vector of map mp[prefixes[i]-‘0’].
- Initialize the vector new_prefixes[].
- Traverse over the map mp[] using the variable x and perform the following tasks:
- Initialize the variable mn as N.
- Traverse the vector x.second using the variable p and perform the following tasks:
- Set the value of mn as the minimum of mn or p.length().
- Traverse the vector x.second using the variable p and perform the following tasks:
- If p.length() is less than equal to mn, then push p into the vector new_prefixes[].
- Iterate over the range [0, new_prefixes.size()) using the variable i and perform the following tasks:
- Subtract the value int(pow(10, N – new_prefixes[i].length())+ 0.5) from the variable total.
- After performing the above steps, print the value of total as the answer.
Below is the implementation of the above approach:
- Python3
- Javascript
// C++ Program to implement the above approach#include <bits/stdc++.h>using namespace std;// Change int to long long in case of overflow!!// Function to calculate total strings of length// N without the given prefixesint totalGoodStrings(int N, vector<string> prefixes){// Calculate total strings presentint total = int(pow(10, N) + 0.5);// Make a map and insert the prefixes with same// character in a vectormap<int, vector<string> > mp;for (int i = 0; i < prefixes.size(); i++) {mp[prefixes[i][0] - '0'].push_back(prefixes[i]);}// Make a new vector of prefixes stringsvector<string> new_prefixes;// Iterate for each starting characterfor (auto x : mp) {int mn = N;// Iterate through the vector to calculate// minimum size prefixfor (auto p : x.second) {mn = min(mn, int(p.length()));}// Take all the minimum prefixes in the new// vector of prefixesfor (string p : x.second) {if (p.length() > mn) {continue;}new_prefixes.push_back(p);}}// Iterate through the new prefixesfor (int i = 0; i < new_prefixes.size(); i++) {// Subtract bad stringstotal -= int(pow(10,N - new_prefixes[i].length())+ 0.5);}return total;}// Driver Codeint main(){int N = 5;vector<string> prefixes= { "1", "0", "911" };cout << totalGoodStrings(N, prefixes);return 0;} |
79900
Time Complexity: O(M), where M is the size of the vector prefixes[]
Auxiliary Space: O(M*K), where K is the maximum length of a string
.png)
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK