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
import math NEW_LINE def perfectSquare ( s ) : NEW_LINE INDENT n = len ( s ) NEW_LINE ans = - 1 NEW_LINE num = " " NEW_LINE for i in range ( 1 , ( 1 << n ) ) : NEW_LINE INDENT str = " " NEW_LINE for j in range ( 0 , n ) : NEW_LINE INDENT if ( ( i >> j ) & 1 ) : NEW_LINE INDENT str = str + s [ j ] NEW_LINE DEDENT DEDENT if ( str [ 0 ] != '0' ) : NEW_LINE INDENT temp = 0 ; NEW_LINE for j in range ( 0 , len ( str ) ) : NEW_LINE INDENT temp = ( temp * 10 + ( ord ( str [ j ] ) - ord ( '0' ) ) ) NEW_LINE DEDENT k = int ( math . sqrt ( temp ) ) NEW_LINE if ( k * k == temp ) : NEW_LINE INDENT if ( ans < len ( str ) ) : NEW_LINE INDENT ans = len ( str ) NEW_LINE num = str NEW_LINE DEDENT DEDENT DEDENT DEDENT if ( ans == - 1 ) : NEW_LINE INDENT return ans NEW_LINE DEDENT else : NEW_LINE INDENT print ( " { } ▁ " . format ( num ) , end = " " ) NEW_LINE return n - ans NEW_LINE DEDENT DEDENT print ( perfectSquare ( "8314" ) ) NEW_LINE print ( perfectSquare ( "753" ) ) ; NEW_LINE