最小可删除的数字，使得一个数字成为完全平方数

问题陈述包括找到从一个数字中删除的最小数字数量，使得该数字成为完全平方数。

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

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

例如，N=42

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

在这个问题中，我们将给定一个数字 N 作为输入，我们的任务是打印通过从 N 中删除最小数量的数字后得到的完全平方数，以及从 N 中删除的数字数量。

有时候，从 N 中删除任意数量的数字后，它可能不能成为一个完全平方数，所以打印−1。如果从 N 中删除最小数量的数字后可以得到多个完全平方数，则打印其中任意一个。

让我们通过下面的例子来理解问题。

输入

N=490

输出

49  1

解释 − 输入的数字是490，不是一个完全平方数。如果我们从数字中移除一个数字，即0，那么数字变为49，这是一个完全平方数（7*7）。同时，如果我们从N中移除两个数字，即9和0，那么数字变为4，也是一个完全平方数。

由于我们需要找到使N成为一个完全平方数所需移除的最小数字数，输出将是49，只需移除1个数字。

输入

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