資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學檢查由所有陣列元素連線而成的數字是否為哈沙德數
在這個問題中，我們給定了一個整數陣列。我們需要將所有元素組合成一個整數，並檢查它是否為哈沙德數。
在我們繼續解決方案之前，讓我們瞭解一下哈沙德數。所有能被其各位數字之和整除的數都是哈沙德數。例如，12是哈沙德數，因為12能被3整除，而3 = 1 + 2。
為了解決這個問題，我們可以組合所有陣列元素，然後檢查結果數字是否為哈沙德數。
問題陳述 – 我們給定了一個整數陣列。我們需要將所有元素組合成一個數字，並檢查組合後的數字是否為哈沙德數。
示例
輸入 – arr = {1, 35, 69, 60};
輸出 – 是
解釋 – 結果數字1356960可以被其各位數字之和整除。
輸入 – arr = {1, 65, 78, 1}
輸出 – 否
解釋 – 組合後的數字165781不能被28整除。
輸入 – arr = {1, 44}
輸出 – 是
解釋 – 144可以被9整除。
方法一
此方法將把所有陣列元素組合成一個字串。之後，我們將使用stoi()方法將組合後的字串轉換為整數。之後，我們可以使用取模運算子來檢查該數字是否可以被其各位數字之和整除。
演算法
定義一個名為“combined”的字串變數，並將其初始化為空字串。
遍歷整數陣列。使用to_string()方法將數字轉換為字串。之後，將其新增到“combined”變數。
定義一個名為“sum”的變數，並將其初始化為零，以儲存各位數字之和。
遍歷組合後的字串，並存儲每個數字的和。
使用stoi()方法將組合後的字串轉換為整數。之後，對整數與總和進行取模運算，並根據結果返回布林值。
示例
#include <iostream>
#include <vector>
using namespace std;
// function to check whether the number formed by concatenating the elements of the array is a Harshad number or not
bool isHarshadNumber(vector<int> array){
// store the concatenated number
string combined = "";
// Iterate over the array
for (auto num : array){
// Concatenate the string
combined += to_string(num);
}
// Stores the sum of digits
int sum = 0;
// Calculate sum of digits
for (int i = 0; i < combined.length(); i++)
sum += (combined[i] - '0');
// Check if n is divisible by the sum
return stoi(combined) % sum == 0;
}
int main(){
// Input
vector<int> arr{1, 35, 69, 60};
if (isHarshadNumber(arr))
cout << "Yes, the number formed by concatenating the array element is a Harshad number";
else
cout << "No, the number formed by concatenating the array element is not a Harshad number";
return 0;
}
輸出
Yes, the number formed by concatenating the array element is a Harshad number
時間複雜度 – O(N)，因為我們遍歷了字串。
空間複雜度 – O(1)，因為我們沒有使用額外的空間。
方法二
在此方法中，我們將對組合整數的每個小塊與總和進行取模運算，並檢查大整數是否可以被其總和整除。
演算法
定義“combined”字串變數。
遍歷整數陣列，組合所有整數，並將它們儲存到“combined”變數中。
將各位數字之和儲存在“sum”變數中
使用迴圈遍歷“combined”字串。
定義“current”變數並將其初始化為零
將“current”變數乘以10，並添加當前數字的值。之後，將結果值儲存到“current”變數中。
對“current”和“sum”進行取模運算。
當迴圈的所有迭代都完成後，如果“current”變數的值為零，則返回true。如果“current”變數的值不為零，則返回false。
示例
#include <iostream>
#include <vector>
using namespace std;
// function to check whether the number formed by concatenating the elements of the array is a Harshad number or not
bool isHarshadNumber(vector<int> array){
// store the concatenated number
string combined = "";
// Iterate over the array
for (auto num : array){
// Concatenate the string
combined += to_string(num);
}
// Stores the sum of digits
int sum = 0;
// Calculate the sum of digits
for (int i = 0; i < combined.length(); i++)
sum += (combined[i] - '0');
// to store the current integer
int current = 0;
for (int i = 0; i < combined.size(); i++) {
// Calculate the current integer by multiplying 10 and adding the current digit
current = current * 10 + (combined[i] - '0');
// Check if the current integer is divisible by the sum
current %= sum;
}
return current == 0;
}
int main(){
// Input
vector<int> arr{1, 35, 69, 0};
if (isHarshadNumber(arr))
cout << "Yes, the number formed by concatenating the array element is a Harshad number";
else
cout << "No, the number formed by concatenating the array element is not a Harshad number";
return 0;
}
輸出
No, the number formed by concatenating the array element is not a Harshad number
時間複雜度 – O(N)
空間複雜度 – O(1)
結論
我們學習了兩種不同的方法來解決這個問題。第一種方法僅在陣列包含較少元素時使用，因為stoi()方法在將字串轉換為整數時有一些限制。第二種方法是通用的，可以用於N個數組元素。
67 次瀏覽
