检查由所有数组元素连接而成的数字是否为哈沙德数

---

在这个问题中，我们给定了一个整数数组。我们需要将所有元素组合成一个整数，并检查它是否为哈沙德数。

在我们继续解决方案之前，让我们了解一下哈沙德数。所有能被其各位数字之和整除的数都是哈沙德数。例如，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个数组元素。