Codeforces•Sep 22, 2025
Make a Square
Hazrat Ali
Codeforces
In one operation you can delete any digit of the given integer so that the result remains a positive integer without leading zeros.
Determine the minimum number of operations that you need to consistently apply to the given integer n to make from it the square of some positive integer or report that it is impossible.
An integer x is the square of some positive integer if and only if x=y2 for some positive integer y.
Input
The first line contains a single integer n (1≤n≤2⋅109). The number is given without leading zeroes.
Output
If it is impossible to make the square of some positive integer from n, print -1. In the other case, print the minimal number of operations required to do it.
Examples
Input
8314
Output
2
Input
625
Output
0
Input
333
Output
-1
Solution
#include <bits/stdc++.h>
#define INF 2000000005
using namespace std;
map<int, int> memo;
int ans = INF;
int solve(int n, int cnt) {
if (memo.count(n) > 0) {
return memo[n];
}
int root = sqrt(n);
if (n > 0 and root * root == n) {
memo[n] = cnt;
return cnt;
}
string ns = to_string(n);
for (int i = 0; i < ns.size(); i++) {
string ms = ns.substr(0, i) + ns.substr(i + 1);
if (ms == "") {
break;
}
int skip = 0;
for (int i = 0; i < ms.size(); i++) {
if (ms[i] == '0') {
skip++;
} else {
break;
}
}
int m = stoi(ms);
ans = min(ans, solve(m, skip + cnt + 1));
}
return min(ans, INF);
}
int main() {
int n;
cin >> n;
int ans = solve(n, 0);
ans = ans == INF ? -1 : ans;
cout << ans << endl;
return 0;
}