# Minimum digits to remove to make a number Perfect Square

Given a integer n, we need to find how many digits remove from the number to make it a perfect square.

Examples :

Input : 8314
Output: 81 2
Explanation: If we remove 3 and 4 number becomes 81 which is a perfect square.

Input : 57
Output : -1

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

The idea is to generate all possible subsequences and return optimal string using set bits. Let’s suppose we have a string 8314. And using set bits we form all possible subsequences i.e.,

8, 3, 83, 1, 81, 31, 831, 4, 84, 34, 834, 14, 814, 314, 8314.

After forming all possible subsequences, we check which one is the perfect square. And we return a perfect square number which has the minimum length.

In above example, three perfect squares are 1 4 and 81, so answer would be 81 because 81 has the max length 2.

## C++

 `// C++ program to find required minimum digits ` `// need to remove to make a number perfect squre ` `#include ` `using` `namespace` `std; ` ` `  `// function to check minimum number of digits ` `// should be removed to make this number ` `// a perfect square ` `int` `perfectSquare(string s) ` `{ ` `    ``// size of the string ` `    ``int` `n = s.size(); ` ` `  `    ``// our final answer ` `    ``int` `ans = -1; ` ` `  `    ``// to store string which is perfect square. ` `    ``string num; ` ` `  `    ``// We make all possible subsequences ` `    ``for` `(``int` `i = 1; i < (1 << n); i++) { ` `        ``string str = ``""``; ` `         `  `        ``for` `(``int` `j = 0; j < n; j++) { ` `             `  `            ``// to check jth bit is set or not. ` `            ``if` `((i >> j) & 1) { ` `                ``str += s[j]; ` `            ``} ` `        ``} ` ` `  `        ``// we do not consider a number with leading zeros ` `        ``if` `(str[0] != ``'0'``) { ` `             `  `            ``// convert our temporary string into integer ` `            ``int` `temp = 0; ` `            ``for` `(``int` `j = 0; j < str.size(); j++) ` `                ``temp = temp * 10 + (``int``)(str[j] - ``'0'``); ` ` `  `            ``int` `k = ``sqrt``(temp); ` ` `  `            ``// checking temp is perfect square or not. ` `            ``if` `(k * k == temp) { ` `                 `  `                ``// taking maximum sized string ` `                ``if` `(ans < (``int``)str.size()) { ` `                    ``ans = (``int``)str.size(); ` `                    ``num = str; ` `                ``} ` `            ``} ` `        ``} ` `    ``} ` ` `  `    ``if` `(ans == -1) ` `        ``return` `ans; ` `    ``else` `{ ` `         `  `        ``// print PerfectSquare ` `        ``cout << num << ``" "``; ` `        ``return` `n - ans; ` `    ``} ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``cout << perfectSquare(``"8314"``) << endl; ` `    ``cout << perfectSquare(``"753"``) << endl;   ` `    ``return` `0; ` `} `

## Java

 `// Java program to find required minimum digits ` `// need to remove to make a number perfect squre ` `import` `java.io.*; ` `import` `java.lang.*; ` ` `  `public` `class` `GFG { ` `     `  `    ``// function to check minimum  ` `    ``// number of digits should  ` `    ``// be removed to make this  ` `    ``// number a perfect square ` `    ``static` `int` `perfectSquare(String s) ` `    ``{ ` `        ``// size of the string ` `        ``int` `n = s.length(); ` `     `  `        ``// our final answer ` `        ``int` `ans = -``1``; ` `     `  `        ``// to store string which ` `        ``// is perfect square. ` `        ``String num = ``""``; ` `     `  `        ``// We make all possible subsequences ` `        ``for` `(``int` `i = ``1``; i < (``1` `<< n); i++) { ` `            ``String str = ``""``; ` `             `  `            ``for` `(``int` `j = ``0``; j < n; j++) { ` `                 `  `                ``// to check jth bit is set or not. ` `                ``if` `(((i >> j) & ``1``) == ``1``) { ` `                    ``str += s.charAt(j); ` `                ``} ` `            ``} ` `     `  `            ``// we do not consider a number  ` `            ``// with leading zeros ` `            ``if` `(str.charAt(``0``) != ``'0'``) { ` `                 `  `                ``// convert our temporary ` `                ``// string into integer ` `                ``int` `temp = ``0``; ` `                ``for` `(``int` `j = ``0``; j <  ` `                              ``str.length(); j++) ` `                    ``temp = temp * ``10` `+  ` `                      ``(``int``)(str.charAt(j) - ``'0'``); ` `     `  `                ``int` `k = (``int``)Math.sqrt(temp); ` `     `  `                ``// checking temp is perfect ` `                ``// square or not. ` `                ``if` `(k * k == temp) { ` `                     `  `                    ``// taking maximum sized string ` `                    ``if` `(ans < (``int``)str.length()) { ` `                        ``ans = (``int``)str.length(); ` `                        ``num = str; ` `                    ``} ` `                ``} ` `            ``} ` `        ``} ` `     `  `        ``if` `(ans == -``1``) ` `            ``return` `ans; ` `        ``else` `{ ` `             `  `            ``// print PerfectSquare ` `            ``System.out.print(num + ``" "``); ` `            ``return` `n - ans; ` `        ``} ` `    ``} ` `     `  `    ``// Driver code ` `    ``public` `static` `void` `main(String args[]) ` `    ``{ ` `        ``System.out.println(perfectSquare(``"8314"``)); ` `        ``System.out.println(perfectSquare(``"753"``)); ` `    ``} ` `} ` ` `  `// This code is contributed by  ` `// Manish Shaw (manishshaw1) `

## Python3

 `# C++ program to find required minimum  ` `# digits need to remove to make a  ` `# number perfect squre ` ` `  `import` `math ` `# function to check minimum number of ` `# digits should be removed to make ` `# this number a perfect square ` `def` `perfectSquare(s) : ` `     `  `    ``# size of the string ` `    ``n ``=` `len``(s) ` ` `  `    ``# our final answer ` `    ``ans ``=` `-``1` ` `  `    ``# to store string which is ` `    ``# perfect square. ` `    ``num ``=` `"" ` ` `  `    ``# We make all possible subsequences ` `    ``for` `i ``in` `range``(``1``, (``1` `<< n)) : ` `        ``str` `=` `"" ` `         `  `        ``for` `j ``in` `range``(``0``, n) : ` `             `  `            ``# to check jth bit is ` `            ``# set or not. ` `            ``if` `((i >> j) & ``1``) : ` `                ``str` `=` `str` `+` `s[j] ` ` `  `        ``# we do not consider a number  ` `        ``# with leading zeros ` `        ``if` `(``str``[``0``] !``=` `'0'``) : ` `             `  `            ``# convert our temporary  ` `            ``# string into integer ` `            ``temp ``=` `0``; ` `            ``for` `j ``in` `range``(``0``, ``len``(``str``)) : ` `                ``temp ``=` `(temp ``*` `10` `+`  `                 ``(``ord``(``str``[j]) ``-` `ord``(``'0'``))) ` ` `  `            ``k ``=` `int``(math.sqrt(temp)) ` ` `  `            ``# checking temp is perfect  ` `            ``# square or not. ` `            ``if` `(k ``*` `k ``=``=` `temp) : ` `                 `  `                ``# taking maximum sized ` `                ``# string ` `                ``if` `(ans < ``len``(``str``)) : ` `                    ``ans ``=` `len``(``str``) ` `                    ``num ``=` `str` ` `  `    ``if` `(ans ``=``=` `-``1``) : ` `        ``return` `ans ` `    ``else` `:          ` `         `  `        ``# print PerfectSquare ` `        ``print` `(``"{} "``.``format``(num), end``=``"") ` `        ``return` `n ``-` `ans ` `     `  `# Driver code ` `print` `(perfectSquare(``"8314"``)) ` `print` `(perfectSquare(``"753"``)); ` ` `  `# This code is contributed by  ` `# manishshaw1. `

## C#

 `// C# program to find required minimum digits ` `// need to remove to make a number perfect squre ` `using` `System; ` `class` `GFG { ` `     `  `    ``// function to check minimum  ` `    ``// number of digits should  ` `    ``// be removed to make this  ` `    ``// number a perfect square ` `    ``static` `int` `perfectSquare(``string` `s) ` `    ``{ ` `        ``// size of the string ` `        ``int` `n = s.Length; ` `     `  `        ``// our final answer ` `        ``int` `ans = -1; ` `     `  `        ``// to store string which ` `        ``// is perfect square. ` `        ``string` `num = ``""``; ` `     `  `        ``// We make all possible subsequences ` `        ``for` `(``int` `i = 1; i < (1 << n); i++) { ` `            ``string` `str = ``""``; ` `             `  `            ``for` `(``int` `j = 0; j < n; j++) { ` `                 `  `                ``// to check jth bit is set or not. ` `                ``if` `(((i >> j) & 1) == 1) { ` `                    ``str += s[j]; ` `                ``} ` `            ``} ` `     `  `            ``// we do not consider a number  ` `            ``// with leading zeros ` `            ``if` `(str[0] != ``'0'``) { ` `                 `  `                ``// convert our temporary ` `                ``// string into integer ` `                ``int` `temp = 0; ` `                ``for` `(``int` `j = 0; j < str.Length; j++) ` `                    ``temp = temp * 10 + (``int``)(str[j] - ``'0'``); ` `     `  `                ``int` `k = (``int``)Math.Sqrt(temp); ` `     `  `                ``// checking temp is perfect ` `                ``// square or not. ` `                ``if` `(k * k == temp) { ` `                     `  `                    ``// taking maximum sized string ` `                    ``if` `(ans < (``int``)str.Length) { ` `                        ``ans = (``int``)str.Length; ` `                        ``num = str; ` `                    ``} ` `                ``} ` `            ``} ` `        ``} ` `     `  `        ``if` `(ans == -1) ` `            ``return` `ans; ` `        ``else` `{ ` `             `  `            ``// print PerfectSquare ` `            ``Console.Write(num + ``" "``); ` `            ``return` `n - ans; ` `        ``} ` `    ``} ` `     `  `    ``// Driver code ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``Console.WriteLine(perfectSquare(``"8314"``)); ` `        ``Console.WriteLine(perfectSquare(``"753"``)); ` `    ``} ` `} ` ` `  `// This code is contributed by  ` `// Manish Shaw (manishshaw1) `

## PHP

 `> ``\$j``) & 1)  ` `            ``{ ` `                ``\$str` `= ``\$str``.``\$s``[``\$j``]; ` `            ``} ` `        ``} ` ` `  `        ``// we do not consider a  ` `        ``// number with leading zeros ` `        ``if` `(``\$str``[0] != ``'0'``)  ` `        ``{ ` `            ``// convert our temporary ` `            ``// string into integer ` `            ``\$temp` `= 0; ` `            ``for` `(``\$j` `= 0; ``\$j` `< ``strlen``(``\$str``); ``\$j``++) ` `                ``\$temp` `= ``\$temp` `* 10 +  ` `                        ``(ord(``\$str``[``\$j``]) - ord(``'0'``)); ` ` `  `            ``\$k` `= (int)(sqrt(``\$temp``)); ` ` `  `            ``// checking temp is perfect ` `            ``// square or not. ` `            ``if` `((``\$k` `* ``\$k``) == ``\$temp``) ` `            ``{ ` `                 `  `                ``// taking maximum sized string ` `                ``if` `(``\$ans` `< ``strlen``(``\$str``))  ` `                ``{ ` `                    ``\$ans` `= ``strlen``(``\$str``); ` `                    ``\$num` `= ``\$str``; ` `                ``} ` `            ``} ` `        ``} ` `    ``} ` ` `  `    ``if` `(``\$ans` `== -1)  ` `        ``return` `\$ans``; ` `    ``else`  `    ``{          ` `        ``// print PerfectSquare ` `        ``echo` `(``\$num``.``" "``); ` `        ``return` `(``\$n` `- ``\$ans``); ` `    ``} ` `}  ` ` `  `// Driver code ` `echo` `(perfectSquare(``"8314"``). ````" "````); ` `echo` `(perfectSquare(``"753"``). ````" "````); ` ` `  `// This code is contributed by  ` `// Manish Shaw (manishshaw1) ` `?> `

Output :

```81 2
-1
```