移除数字使其成为完全平方数的最小位数

---

问题陈述包括找到从数字中移除的最小数字数量，以使数字成为完全平方数。

完全平方数表示为 $\mathrm{x^{2}}$ 是一个正整数，它是整数与其自身的乘积。

我们将得到一个正数 N，我们需要找到我们可以从数字 N 中移除的最小数字数量，以使其成为完全平方数，即它是某个整数与其自身的乘积。

例如，N=42

我们可以从 N 中移除 1 位数字，即 2，使其成为完全平方数，这将是 4，这是一个完全平方数。

在这个问题中，我们将得到一个数字 N 作为输入，我们的任务将是从 N 中移除最小数量的数字并打印完全平方数，以及从 N 中移除的数字数量以使其成为完全平方数。

在某些情况下，在从 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 的最长子序列，该子序列在我们的 C++ 方法中是完全平方数，以获得要移除的最小数字和数字。

• 我们将初始化两个变量来存储是完全平方数的数字和要移除的最小数字数量。

• 我们将使用 to_string() 函数将输入数字 N 转换为字符串，并调用递归函数，该函数将为我们提供最长可能长度的完全平方数。

• 打印完全平方数和移除的最小数字。

示例

//C++ code to find the minimum number of digits to be removed to make N a perfect square
#include<bits/stdc++.h>

using namespace std;

int res=-1; //to store perfect square after removing digits from N
int a=0; //to store the number of digits in perfect square

//to check if the subsequence is a perfect square of maximum length possible
void checkMaximum(int m,string ans)
{
    
    
       int check=sqrt(m); //finding square root of subsequence
       
         if(check*check==m) 
         {
           if(a < ans.size()) //if length of subsequence is greater than a
           {
               a = ans.size(); //store length of subsequence in a
               res = m; //store number in res which is a perfect square
           }
         }
         
}

//to find all the possible subsequences
void subsequence(string str,string ans){
    
    if(str.length() == 0){
        
        if( !ans.empty()){
            
         int temp = stoi(ans); //converting subsequence in int 
         
         checkMaximum(temp, ans); //checking if it is the perfect square by removing minimum digits
        
        }
     return;
    }
        //generating all the possible subsequences using recursion
        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); //converting N into a string using inbuilt function
   string ans =""; //string to store all the possible subsequences of N

   //calling the function
   subsequence(str, ans);
   
   if(res==-1){
       cout<<res<<endl;
   }
   else{
   cout<<res<<endl;
   //difference of str size and a which is the length of perfect square will give minimum number of digits
   cout<<str.size()-a<<endl;
   }
  
    return 0;
}

输出

784
2

时间复杂度− $\mathrm{O(2^{n})}$，其中 n 是递归树的深度。

空间复杂度− $\mathrm{O(2^{n})}$，因为递归函数使用堆栈内存。

结论

本文讨论了查找要从 N 中移除的最小数字数量以使其成为完全平方数的问题。我们使用递归检查 N 的所有子序列，以检查每个子序列是否是我们 C++ 方法中最长可能长度的完全平方数，以获得要移除的最小数字和数字。

我希望您在阅读本文后已经了解了问题和解决问题的方法。