要使一个数成为完全平方数，需要删除的最少位数
问题描述包括找出要使一个数成为完全平方数，需要删除的最少位数。
完全平方数表示为 $\mathrm{x^{2}}$，它是一个正整数，它是一个整数与其自身的乘积。
给定一个正数 N，我们需要找出可以从 N 中删除的最少位数，使其成为完全平方数，即某个整数与其自身的乘积。
例如，N=42
我们可以从 N 中删除 1 位数字，即 2，使其成为完全平方数，也就是 4，也是一个完全平方数。
在这个问题中，我们将给定一个数字 N 作为输入，我们的任务是通过从 N 中删除最少位数的数字和从 N 中移除 1 位数字，使其成为一个完全平方数。
在某些情况下，从 N 中移除任意位数的数字后，它仍然不是完全平方数，因此打印 -1。如果通过移除最少位数的数字可以形成多个完全平方数，则打印其中任意一个。
让我们通过以下示例来理解这个问题。
输入
N=490
输出
49 1
解释- 输入数字为 490，它不是完全平方数。如果我们从数字中移除一位数字，即 0，则数字变为 49，即一个完全平方数 (7*7)。同时，如果我们从 N 中移除两位数字，即 9 和 0，该数字将变为 4，这也是一个完全平方数。
由于我们需要找到最少移除的位数才能使 N 成为完全平方数，因此仅移除 1 位数字，输出将为 49。
输入
N=323
输出
-1
解释- 给定的数字是 323，它不是完全平方数，即使从 N 中移除任意位数，也无法使其成为完全平方数。因此，输出为 -1。
让我们理解一下算法，找出从 N 中移除的最少位数，使其成为完全平方数。
算法
我们需要通过移除任意位数，使给定的数字 N 成为完全平方数。我们需要找出移除的最少位数，才能使其成为完全平方数。
为了找出从 N 中移除的最少位数，使其成为一个完全平方数，我们只需找到数字 N 的所有子序列即可。例如，假设 N 为 8641，则该数字的所有子序列为
8、6、4、1、86、84、81、64、61、41、864、861、841、641、8641。
我们将检查每个子序列是否为完全平方数，并找出从 N 中移除最少位数后可以形成的完全平方数子序列。完全平方数为 4、81、64 和 841。为了使其成为完全平方数，需要从 N 中移除的最少位数为 1，即 6。 841.
为了找到 N 的所有可能子序列，我们将使用递归的概念来查找所有子序列。我们创建一个函数来查找数字 N 的子序列，其中我们将传递一个字符串数据类型的数字和一个空字符串。
递归函数的边界条件是，当字符串长度为 0 时，我们将返回该函数。否则，我们将字符串的第一个字符存储在一个变量中，并更新字符串，但不包括第一个字符。然后，我们将调用相同的函数，传递更新后的字符串，并在 ans 字符串中添加字符，然后不添加 ans 字符串，最终将生成数字的所有可能子序列。
一旦数字的字符串长度为 0，即我们找到了 N 的一个可能子序列，如果 ans 字符串不为空，我们将调用一个函数，通过从 N 中删除最少位数来检查它是否是一个完全平方数。
我们将初始化两个变量，分别存储使 N 成为完全平方数所需删除的最少位数，以及在函数外部存储的完全平方数 N，以获得所需的输出。
为了找到通过删除 N 的最少位数而得到的完全平方数，我们将子序列的平方根存储在一个 int 数据类型的变量中。如果变量的平方等于数字，我们将检查子序列的长度是否大于 a，然后将子序列的长度存储在 a 中，并将子序列存储在另一个变量中。
这样，我们可以得到 N 的所有子序列，并找到最大长度的子序列，该子序列与 N 的大小之差将给出使 N 成为完全平方数所需移除的最小位数。
方法
为了找到使 N 成为完全平方数所需移除的最小位数，我们按照以下步骤实现我们方法中的算法:
为了计算 N 的所有可能子序列，我们调用一个递归函数，对于每个子序列，我们将检查它是否是 N 的最长子序列，即完全平方数。
我们将初始化两个变量来存储数字它是一个完全平方数，并且需要移除的位数最少。
我们将使用 to_string() 函数将输入数字 N 转换为字符串，并调用递归函数，该函数将返回最长可能长度的完全平方数。
打印完全平方数和移除的最少位数。
示例
//C++ 代码，用于查找使 N 成为完全平方数所需的最少移除位数
#include<bits/stdc++.h>
using namespace std;
int res=-1; //从 N 中移除数字后存储完全平方数
int a=0; //存储完全平方数的位数
//检查子序列是否为最大长度的完全平方数
void checkMaximum(int m,string ans)
{
int check=sqrt(m); //求子序列的平方根
if(check*check==m)
{
if(a < ans.size()) //如果子序列的长度大于
{
a = ans.size(); //将子序列的长度存储在
res = m; //将数字存储在 res 中，这是一个完全平方数
}
}
}
// 查找所有可能的子序列
void subsequence(string str,string ans){
if(str.length() == 0){
if( !ans.empty()){
int temp = stoi(ans); //将子序列转换为 int
checkMaximum(temp, ans); //通过删除最小数字来检查它是否是完全平方数
}
return;
}
//使用递归生成所有可能的子序列
char ch = str[0];
string roq = str.substr(1);
subsequence(roq, ans + ch);
subsequence(roq, ans);
}
int main()
{
int N=78467;
string str =to_string(N); //使用内置函数将 N 转换为字符串
string ans =""; //用于存储 N 所有可能子序列的字符串
//调用函数
subsequence(str, ans);
if(res==-1){
cout<<res<<endl;
}
else{
cout<<res<<endl;
//str 大小与完全平方的长度之差将给出最少位数
cout<<str.size()-a<<endl;
}
return 0;
}
输出
784 2
时间复杂度− $\mathrm{O(2^{n})}$，其中 n 是递归树的深度。
空间复杂度− $\mathrm{O(2^{n})}$，因为递归函数使用堆栈内存。
结论
本文讨论了从 N 中找出需要移除的最少数字，以使其成为完全平方数的问题。我们用 C++ 方法生成了 N 的所有子序列，并对每个子序列进行递归检查，以确定其是否是长度尽可能长的完全平方数，从而得到需要移除的最少数字和最终结果。
希望您在阅读本文后能够理解这个问题以及解决问题的方法。
