用C++生成由M个数字组成的能被5整除的N位数

给定一个数字N和一个包含M个数字的数组，我们的任务是找到由给定的M个数字组成的、能被5整除的N位数的个数。

让我们看一些例子来理解问题的输入和输出。

输入：

N = 2
M = 3
arr = {5, 6, 3}

输出：

2

有2个能被5整除的N位数：35和65。让我们看另一个例子。

输入：

N = 1
M = 7
arr = {2, 3, 4, 5, 6, 7, 8}

输出：

1

在给定的数组中，只有一个1位数能被5整除。所以，我们的任务是找到可以由给定数字组成的、能被5整除的N位数的个数。

为了能被5整除，这个数必须以0或5结尾。让我们看看算法

算法

  • 1. 检查给定数组中是否存在0和5。2. 如果同时存在0和5，则有两种方法将数字放在个位数。否则，只有一种方法将数字放在个位数。
    • 将计数初始化为2。
    • 现在，剩余的位置分别有m - 1, m - 2, m - 3, ... n种方法填充。
    • 编写一个从0迭代到n - 1的循环。
      • 递减数组的大小。
      • 将它乘以计数。
  • 如果只有一个数字0或5，则只有一种方法将数字放在个位数。
    • 将计数初始化为2。
    • 现在，剩余的位置分别有m - 1, m - 2, m - 3, ... n种方法填充。
    • 编写一个从0迭代到n - 1的循环。
      • 递减数组的大小。
      • 将它乘以计数。
  • 如果没有数字0或5，则我们无法构成能被5整除的数。在这种情况下返回-1。

实现

以下是上述算法在C++中的实现

#include <bits/stdc++.h>

using namespace std;

int numbers(int n, int m, int arr[]) {
   bool isZeroPresent = false, isFivePresent = false;
   int numbersCount = 0;
   if (m < n) {
      return -1;
   }
   for (int i = 0; i < m; i++) {
      if (arr[i] == 0) {
         isZeroPresent = true;
      }
      if (arr[i] == 5) {
         isFivePresent = true;
      }
   }
   if (isZeroPresent && isFivePresent) {
      numbersCount = 2;
      for (int i = 0; i < n - 1; i++) {
         m--;
         numbersCount = numbersCount * m;
      }
   } else if (isZeroPresent || isFivePresent) {
      numbersCount = 1;
      for (int i = 0; i < n - 1; i++) {
         m--;
         numbersCount = numbersCount * m;
      }
   } else {
      return -1;
   }
   return numbersCount;
}
int main() {
   int arr[] = {5, 6, 3};
   cout << numbers(2, 3, arr) << endl;
   return 0;
}

输出

如果您运行以上代码，您将得到以下结果。

2

更新于：2021年10月21日

142 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告