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