首页 > 文章列表 > 全能数码产品

全能数码产品

物联网 虚拟现实 智能家居
167 2023-09-09

给定两个数字,我们的任务是找出给定的数字是否是通过将另外两个数字相乘获得的,使得所有三个数字一起构成一个 9 位泛数字。

换句话说,可以说我们必须找出给定的数字与另外两个数字相结合后是否形成乘法运算得到原始数字的全数字。

我们可能会遇到很多这样的情况,我们将获得该问题的多个解决方案,为了获得最佳时间复杂度,我们将简单地打印找到的第一个解决方案并停止迭代过程。

解决方案:首先让我们讨论什么是全数字数 -

当且仅当一个 n 位数字仅使用 1 到 n 的所有数字一次时,该数字才能称为泛数字。即,该数字可以表示为仅使用一位数字一次从 1 到 n 的所有数字的排列。

例如,6745312 是一个 7 位泛数字,因为它使用从 1 到 7 的所有数字

现在让我们用几个例子来理解这个问题 -

Given Number: 7254
Result obtained: Yes, the condition is true

众所周知,7254 可以表示为 39 和 186 的乘积。

将39、186和7254相加,我们得到391867254,其中包含了从1到9的所有数字,每个数字只使用一次,即它是一个由9个数字组成的全数字数。

Given Number: 6952
Result obtained: Yes, the condition is true

方法

现在,让我们讨论解决这个问题的方法−

我们首先找出所有乘积等于给定数字的数对进行检查。然后对于每个可能的解数对,我们将创建一个字符串并存储所有三个数字(原始数字和导致乘积为该数字的两个因子)。

现在让我们寻找适合我们解决方案的工作算法。

  • 第 1 步 - 迭代循环以检查该数字的所有因子对。

  • 第二步 − 对于因子的每个部分,我们将创建一个包含原始数字和两个因子的字符串。

  • 第三步 - 使用sort()函数对形成的字符串进行排序。

  • 第 4 步 - 现在我们将创建另一个字符串“123456789”

  • 第 5 步 - 比较两个字符串,如果相同则返回 true。

示例

此方法的代码如下 -

#include <bits/stdc++.h>
using namespace std;

// this function checks whether the given string consist of pandigital numbers
bool Is_Pandigital_product (string Original_string) {
   if ( Original_string.length() != 9 ) {
      return false;
   }
   char c[Original_string.length()];
   strcpy(c, Original_string.c_str());
   sort(c, c + Original_string.length());
   string new_string = c;
   if(new_string.compare("123456789") == 0) // comparing both the strings
   {
      return true;
   } else {
      return true;
   }
}
bool PandigitalProduct_1_9(int num)
// This function iterates over a loop till Sqrt(n) and searches for factors of given input.
// for each factor, this loop calls for Is_Pandigital_product function
{
   for (int Iterator = 1; Iterator * Iterator <= num; Iterator++)
      if (num % Iterator == 0 && Is_Pandigital_product(to_string(num) + to_string(Iterator) + to_string(num / Iterator)))
   return true; //Returns true if found pandigital number
   return false;
}
int main() {
   int num = 1234;
   if (PandigitalProduct_1_9(num) == true)
      cout << "yes the number " << num << " is a pandigital product";
   else
      cout << "no the number " << num <<" is not a pandigital product";
    return 0;
}

输出

yes the number 1234 is a pandigital product

时间复杂度 - 由于我们使用了从 1 迭代到 sqrt(n) 的单个循环,因此该解决方案的时间复杂度将为 O(N^1/2)

空间复杂度 - 由于代码不需要任何额外的内存,空间复杂度是线性的,即 O(1)。

在这篇文章中,我们研究了什么是全数字数以及一种高效的方法来判断给定数字及其因子(成对)在相乘后组合成一个字符串后是否得到一个9位全数字数。