首頁 >後端開發 >C++ >全能數位產品

全能數位產品

WBOY
WBOY轉載
2023-09-19 13:09:10977瀏覽

全能數位產品

給定兩個數字,我們的任務是找出給定的數字是否是透過將另外兩個數字相乘而獲得的,使得所有三個數字一起構成一個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位全數字數。

以上是全能數位產品的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文轉載於:tutorialspoint.com。如有侵權,請聯絡admin@php.cn刪除