C++程序 检查所有数组元素是否可以通过旋转数字转换为pronic数
给定大小为N的数组 arr [] ,任务是通过任意次数旋转数组元素的数字来检查是否可能将所有数组元素转换为pronic数。
示例:
输入:{ 321, 402, 246, 299}
输出: True
解释:
arr [0]→右旋一次将arr [0]修改为132(= 11×12)。
arr [1]→右旋一次将arr [0]修改为240(= 15×16)。
arr [2]→右旋两次,将arr [2]修改为462(= 21×22)。
arr [3]→右旋两次将arr [3]修改为992(= 31×32)。
输入:{ 433, 653, 402, 186}
输出: False
方法: 按照以下步骤解决问题:
- 遍历数组并检查每个数组元素是否可以转换为Pronic数。
- 对于每个数组元素,应用所有可能的旋转,并检查每次旋转后生成的数字是否为Pronic数。
- 如果无法将任何数组元素转换为Pronic数,请打印 “False” 。
- 否则,请打印 “True” 。
下面是上述方法的实现:
// 上述方法的C ++程序
#include
using namespace std;
// 检查Pronic Number的函数
bool isPronic(int x)
{
for (int i = 0; i < (int)(sqrt(x)) + 1; i++)
{
// 通过连续相乘检查Pronic Number
if (x == i * (i + 1))
{
return true;
}
}
return false;
}
// 检查val的任何排列是否为Pronic数
bool checkRot(int val)
{
string temp = to_string(val);
for (int i = 0; i < temp.length(); i++)
{
if (isPronic(stoi(temp)) == true)
{
return true;
}
temp = temp.substr(1, temp.size() - 1) + temp[0];
}
return false;
}
// 检查所有数组元素是否可以转换为Pronic数的函数
bool check(int arr[], int N)
{
// 遍历数组
for (int i = 0; i < N; i++)
{
// 如果当前元素无法转换为Pronic数
if (checkRot(arr[i]) == false)
{
return false;
}
}
return true;
}
// 驱动程序
int main()
{
// 给定数组
int arr[] = { 321, 402, 246, 299 };
int N = sizeof(arr) / sizeof(arr[0]);
// 调用函数
cout << (check(arr, N) ? "True" : "False");
return 0;
}
输出:
True
时间复杂度: O(N 3/2 )
辅助空间: O(1)