Split the number N by maximizing the count of subparts divisible by K | Function to count the subparts ; Total subStr till now ; If it can be divided , then this substring is one of the possible answer ; Convert string to long long and check if its divisible with X ; Consider there is no vertical cut between this index and the next one , hence take total carrying total substr a . ; If there is vertical cut between this index and next one , then we start again with subStr as " " and add b for the count of subStr upto now ; Return max of both the cases ; Driver code
def count ( N , X , subStr , index , n ) : NEW_LINE INDENT if ( index == n ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT a = subStr + N [ index ] NEW_LINE b = 0 NEW_LINE if ( int ( a ) % X == 0 ) : NEW_LINE INDENT b = 1 NEW_LINE DEDENT m1 = count ( N , X , a , index + 1 , n ) NEW_LINE m2 = b + count ( N , X , " " , index + 1 , n ) NEW_LINE return max ( m1 , m2 ) NEW_LINE DEDENT N = "00001242" NEW_LINE K = 3 NEW_LINE l = len ( N ) NEW_LINE print ( count ( N , K , " " , 0 , l ) ) NEW_LINE