Checks whether the number formed by concatenating array elements is a hashed number

In this question, we are given an array of integers. We need to combine all the elements into an integer and check if it is a Harshad number.

Before we move on to the solution, let us understand the Harshad number. All numbers are Harshad numbers, which are divisible by the sum of their numbers. For example, 12 is Harshad's number because 12 is divisible by 3, which is the sum of 1 2.

To solve this problem, we can add all the array elements and then check whether the result is a Harshad number.

Problem Statement - We are given an array of integers. We need to combine all the elements into a number and check if the combined number is a Harshad number.

Example

Input– arr = {1, 35, 69, 60};

Output-Yes

Explanation - The resulting number 1356960 is divisible by its sum.

Input – arr = {1, 65, 78, 1}

Output – No

Note – The combined number 165781 is not divisible by 28.

Input – arr = {1, 44}

Output-Yes

Explanation——144 is divisible by 9.

method 1

This method combines all array elements into a string. We will then use the stoi() method to convert the combined strings into integers. Afterwards, we can use the modulo operator to check if a number is divisible by the sum of its digits.

algorithm

• Define a "combined" string variable and initialize it with an empty string.

• Iterate over an array of integers. Convert a number to a string using the to_string() method. After that, append it to the "combined" variable.

• Define the variable 'sum' and initialize it to zero to store the sum of numbers.

• Loop through the combined string and store the sum of each number.

• Use the stoi() method to convert the combined string to an integer. Afterwards, the integer is taken modulo and a Boolean value is returned based on the result.

Example

#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;
}

Output

Yes, the number formed by concatenating the array element is a Harshad number

Time complexity - O(N), since we iterate over the string.

Space Complexity - O(1) since we don't use extra space.

Method 2

In this method, we will perform the modulo operation on each small block of the combined integer and check whether the large integer is divisible by its sum.

algorithm

• Define "combined" string variables.

• Iterate over the integer array and store all integer combinations into the 'combined' variable.

• Store the sum of numbers in the "sum" variable

• Use a loop to iterate over the "combined" string.

• Define the 'current' variable and initialize it to zero

• Multiply the 'current' variable by 10 and add the current numeric value. Then, store the resulting value in the 'current' variable.

• Perform modulo operation on ‘current’ and sum.

• When all iterations of the loop are completed, return true if the value of the "current" variable is zero. Returns false if the current variable's value is non-zero.

Example

#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;
}

Output

No, the number formed by concatenating the array element is not a Harshad number

Time complexity - O(N)

Space complexity - O(1)

in conclusion

We learned two different ways to solve the problem. The first method is only used when the array contains fewer elements, since the stoi() method has some limitations when converting strings to integers. The second method is general and can be used for N array elements.

The above is the detailed content of Checks whether the number formed by concatenating array elements is a hashed number. For more information, please follow other related articles on the PHP Chinese website!