Largest number N which can be reduced to 0 in K steps | Utility function to return the first digit of a number . ; Remove last digit from number till only one digit is left ; return the first digit ; Utility function that returns the count of numbers written down when starting from n ; Function to find the largest number N which can be reduced to 0 in K steps ; Get the sequence length of the mid point ; Until k sequence length is reached ; Update mid point ; Get count of the new mid point ; Update right to mid ; Update left to mid ; Increment mid point by one while count is equal to k to get the maximum value of mid point ; Driver Code
def firstDigit ( n ) : NEW_LINE INDENT while ( n >= 10 ) : NEW_LINE INDENT n //= 10 ; NEW_LINE DEDENT return n ; NEW_LINE DEDENT def getCount ( n ) : NEW_LINE INDENT count = 1 ; NEW_LINE while ( n != 0 ) : NEW_LINE INDENT leadDigit = firstDigit ( n ) ; NEW_LINE n -= leadDigit ; NEW_LINE count += 1 ; NEW_LINE DEDENT return count ; NEW_LINE DEDENT def getLargestNumber ( k ) : NEW_LINE INDENT left = k ; NEW_LINE right = k * 10 ; NEW_LINE mid = ( left + right ) // 2 ; NEW_LINE length = getCount ( mid ) ; NEW_LINE while ( length != k ) : NEW_LINE INDENT mid = ( left + right ) // 2 ; NEW_LINE length = getCount ( mid ) ; NEW_LINE if ( length > k ) : NEW_LINE INDENT right = mid ; NEW_LINE DEDENT else : NEW_LINE INDENT left = mid ; NEW_LINE DEDENT DEDENT while ( length == k ) : NEW_LINE INDENT if ( length != getCount ( mid + 1 ) ) : NEW_LINE INDENT break ; NEW_LINE DEDENT mid += 1 ; NEW_LINE DEDENT return mid ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT k = 3 ; NEW_LINE print ( getLargestNumber ( k ) ) ; NEW_LINE DEDENT