Count the number of N-digit numbers that do not have a given prefix

The problem here is to determine the total number of characters '0' to '9' contained in a string of length N, providing an integer N and a string prefix array pre[] , such that none of these strings contains the provided prefix. The purpose of this article is to implement a program that finds the number of N-digit numbers that does not have a given prefix.

In the C programming language, a set of distinct strings is called an array because an array is a linear combination of a set of data fragments of similar types.

As we already know, the string is a character-by-character, one-dimensional array that ends with an empty or a null character.

Example Example 1

Let us assume that the input N = 2,

The given prefix, pre = {“1”}

Output obtained: 90

explain

Here, except {"01","10","11", "12", "13", "14", "15", "16", "17", "18", "19 ", "21", "31", "41", "51", "61", "71", "81", "91"} are valid.

Example Example 2

Let us take the input value N = 3 as an example.

The given prefix, pre = {“56”}

Output obtained: 990

explain

Here, except {"560", "561", "562", "563", "564", "565", "566", "567", "568", "569"} All 3-digit strings are valid.

ExampleExample 3

Let’s look at an input N = 1,

The given prefix, pre = {“6”}

Output obtained: 9

explain

Except {"6"}, all 1-digit strings here are valid.

Problem Statement

Implement a program to find the number of N-digit numbers that does not have a given prefix.

method

To find the number of N digits without a given prefix, we use the following method.

Solve this problem and find the way to N number of digits that does not have the given prefix

Considering that there are 10 character options at each position in the string, there are (10N) potential strings in total. Instead of counting the total number of strings you want, subtract the total number of strings you don't want. Merging prefixes with the same initial characters into a longer prefix before iteration may result in the removal of some duplicates.

algorithm

Finding algorithm for counting N digits that does not have the following given prefix

• First Step − Start

• Step 2 - Define a function to count the total number of strings of length N that do not contain the given prefix

• Step 3 - Calculate the total number of existing strings

• Step 4 - Create an array and counters a and aCount and insert these prefixes into it

• Step 5 − Create a new prefix string array

• Step 6 - Iterate for each starting character

• Step 7 - Iterate over the array to calculate the minimum size of the prefix

• Step 8 - Now put all these minimal prefixes into a new prefix array

• Step 9 - Iterate over new prefixes

• Step 10 - Deduct unnecessary strings

• Step 11 − Print the obtained results

• Step 12 − Stop

Example: C program

This is a C program implementation of the above algorithm to find the number of N digits that does not have a given prefix.

#include <stdio.h>
#include <math.h>
#include <string.h>
#define MAX_LENGTH 10

// Function to calculate total strings of length N without the given prefixes
int totalStrings(int N, char pre[][MAX_LENGTH], int pre_Count){

   // Calculate total strings present
   int total = (int)(pow(10, N) + 0.5);
   
   // Make an array and counter a and aCount respectively and insert these prefixes with same character in the array
   char a[10][MAX_LENGTH];
   int aCount[10] = {0};
   for (int i = 0; i < pre_Count; i++)    {
      int index = pre[i][0] - '0';
      strcpy(a[index] + aCount[index] * MAX_LENGTH, pre[i]);
      aCount[index]++;
   }
   
   // Make a new array of prefixes strings
   char new_pre[pre_Count][MAX_LENGTH];
   int new_pre_count = 0;
   
   // Iterating for  each of the starting //character
   for (int x = 0; x < 10; x++){
      int m = N;
      
      // Iterate over the array to calculate minimum size prefix
      for (int j = 0; j < aCount[x]; j++){
         int p_length = strlen(a[x] + j * MAX_LENGTH);
         m = (m < p_length) ? m : p_length;
      }
      
      // now take all these minimum prefixes in the new array of prefixes
      for (int j = 0; j < aCount[x]; j++){
         int p_length = strlen(a[x] + j * MAX_LENGTH);
         if (p_length <= m){
            strcpy(new_pre[new_pre_count], a[x] + j * MAX_LENGTH);
            new_pre_count++;
         }
      }
   }
   
   // Iterating through the new prefixes
   for (int i = 0; i < new_pre_count; i++){
   
      // Subtract the unwanted strings
      total -= (int)(pow(10, N - strlen(new_pre[i])) + 0.5);
   }
   return total;
}

// The main function
int main(){
   int N = 5;
   char pre[][MAX_LENGTH] = {"1", "0", "2"};
   int pre_Count = sizeof(pre) / sizeof(pre[0]);
   printf("%d\n", totalStrings(N, pre, pre_Count));
   return 0;
}

Output

70000

in conclusion

Similarly, we can find the number of N digits that does not have the given prefix.

In this post, the challenge of getting a program to find an N-digit count that does not have a given prefix is ​​addressed.

C programming code is provided here along with the algorithm to find the count of N-digit numbers that do not have a given prefix.

The above is the detailed content of Count the number of N-digit numbers that do not have a given prefix. For more information, please follow other related articles on the PHP Chinese website!