Largest number N which can be reduced to 0 in K steps | C ++ program to implement above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int firstDigit ( int n ) { while ( n >= 10 ) { n /= 10 ; } return n ; } int getCount ( int n ) { int count = 1 ; while ( n != 0 ) { int leadDigit = firstDigit ( n ) ; n -= leadDigit ; count ++ ; } return count ; } int getLargestNumber ( int k ) { int left = k ; int right = k * 10 ; int mid = ( left + right ) / 2 ; int len = getCount ( mid ) ; while ( len != k ) { mid = ( left + right ) / 2 ; len = getCount ( mid ) ; if ( len > k ) { right = mid ; } else { left = mid ; } } while ( len == k ) { if ( len != getCount ( mid + 1 ) ) { break ; } mid ++ ; } return ( mid ) ; } int main ( ) { int k = 3 ; cout << getLargestNumber ( k ) ; return 0 ; }