C++ 不具有给定前缀的N位数的计数

在这里，问题是确定长度为N的字符串总数，其中包含字符’0’到’9’，给定一个整数N和一个字符串前缀数组pre []，使得这些字符串不能包含给定的前缀。本文的目标是实现一个程序，以找到不具有给定前缀的N位数的计数。

在C编程语言中，一个包含各种字符串的集合被称为数组，因为数组是具有相似类型的数据片段的线性分组。

正如我们已经知道的，字符串是一个逐个字符的一维数组，以空字符或空字符结尾。

示例1

假设输入N = 2

The given prefix, pre = {“1”}

Output obtained: 90

解释

所有除了{“01”, “10”, “11”, “12”, “13”, “14”, “15”, “16”, “17”, “18”, “19”, “21”, “31”, “41”, “51”, “61”, “71”, “81”, “91”}以外的两位数字字符串都是有效的。

示例2

让我们输入N = 3。

The given prefix, pre = {“56”}

Output obtained: 990

解释

这里的有效字符串是除了{“560”, “561”, “562”, “563″, “564”, “565”, “566”, “567”, “568”, “569”}之外的所有3位数字串。

示例3

假设输入N = 1。

The given prefix, pre = {“6”}

Output obtained: 9

解释

这里的所有1位数字符串，除了{“6”}，都是有效的。

问题陈述

实现一个程序，找到没有给定前缀的N位数字的数量。

方法

为了找到没有给定前缀的N位数字的数量，我们使用以下方法。

解决这个问题并找到没有给定前缀的N位数字的数量的方法。

给定字符串中每个位置都有10个字符选项，总共有(10N)个潜在的字符串。而不是计算想要的字符串的总数，减去不想要的字符串的总数。将前缀与较长前缀的相同初始字符合并在迭代前缀之前，可能会导致某些重复的删除。

步骤

找到没有给定前缀的N位数字的数量的算法如下：

步骤1 − 开始
步骤2 − 定义函数来计算长度为N的字符串的总数，不包括给定的前缀
步骤3 − 计算出现的总字符串
步骤4 − 创建数组和计数器a和aCount，分别插入这些具有相同前缀的前缀
步骤5 − 创建一个新的前缀字符串数组
步骤6 − 对每个起始字符进行迭代
步骤7 − 遍历数组，计算最小大小前缀
步骤8 − 现在将所有这些最小前缀放入新的前缀数组中
步骤9 − 遍历新的前缀
步骤10 − 减去不想要的字符串
步骤11 − 打印所得到的结果
步骤12 − 停止

示例：C程序

这是上述算法的C程序实现，用于找到没有给定前缀的N位数字的数量。

#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;
}