資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學全數字產品
給定兩個數字，我們的任務是確定給定數字是否由另外兩個數字相乘得到，並且這三個數字組合在一起構成一個 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 - 迭代迴圈以檢查數字的所有因數對。
步驟 2 - 對於每個因數對，我們將建立一個包含原始數字和兩個因數的字串。
步驟 3 - 使用 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 位全數字。
191 次檢視
