给定两个数字 N 和 D .任务是找出小于或等于 N 其中包含尾随9的最大数量，且N与该数字之间的差值不应大于 D . 例如：
null
Input: N = 1029, D = 102Output: 9991029 has 1 trailing nine while 999 has three trailing nine.Also 1029-999 = 30(which is less than 102).Input: N = 10281, D = 1Output: 10281
A. 幼稚的方法 将从N迭代到N-D，并找到尾随9的最大数。 通过一些关键观察，可以找到一种有效的方法。对这个问题的一个关键观察是，最大的数字小于 N 以至少一句话结束( K )九是
[n–（n模10^k）–1]
从N到1的总位数开始遍历k的所有可能值，并检查d是否>N% 
.如果未获得此类值，则最终答案将为N本身。否则，使用上述观察结果检查答案。 以下是上述方法的实施情况。
C++
// CPP to implement above function #include <bits/stdc++.h> using namespace std; // It's better to use long long // to handle big integers #define ll long long // function to count no of digits ll dig(ll a) { ll count = 0; while (a > 0) { a /= 10; count++; } return count; } // function to implement above approach void required_number(ll num, ll n, ll d) { ll i, j, power, a, flag = 0; for (i = num; i >= 1; i--) { power = pow (10, i); a = n % power; // if difference between power // and n doesn't exceed d if (d > a) { flag = 1; break ; } } if (flag) { ll t = 0; // loop to build a number from the // appropriate no of digits containing only 9 for (j = 0; j < i; j++) { t += 9 * pow (10, j); } // if the build number is // same as original number(n) if (n % power == t) cout << n; else { // observation cout << n - (n % power) - 1; } } else cout << n; } // Driver Code int main() { ll n = 1029, d = 102; // variable that stores no of digits in n ll num = dig(n); required_number(num, n, d); return 0; } |
JAVA
// Java code to implement above function import java.io.*; class GFG { // It's better to use long // to handle big integers // function to count no. of digits static long dig( long a) { long count = 0 ; while (a > 0 ) { a /= 10 ; count++; } return count; } // function to implement above approach static void required_number( long num, long n, long d) { long i, j, power= 1 , a, flag = 0 ; for (i = num; i >= 1 ; i--) { power = ( long )Math.pow( 10 , i); a = n % power; // if difference between power // and n doesn't exceed d if (d > a) { flag = 1 ; break ; } } if (flag> 0 ) { long t = 0 ; // loop to build a number from the // appropriate no of digits containing // only 9 for (j = 0 ; j < i; j++) { t += 9 * Math.pow( 10 , j); } // if the build number is // same as original number(n) if (n % power == t) System.out.print( n); else { // observation System.out.print( n - (n % power) - 1 ); } } else System.out.print(n); } // Driver Code public static void main (String[] args) { long n = 1029 , d = 102 ; // variable that stores no // of digits in n long num = dig(n); required_number(num, n, d); } } // This code is contributed by chandan_jnu |
Python3
# Python3 to implement above function # function to count no of digits def dig(a): count = 0 ; while (a > 0 ): a / = 10 count + = 1 return count # function to implement above approach def required_number(num, n, d): flag = 0 power = 0 a = 0 for i in range (num, 0 , - 1 ): power = pow ( 10 , i) a = n % power # if difference between power # and n doesn't exceed d if (d > a): flag = 1 break if (flag): t = 0 # loop to build a number from the # appropriate no of digits containing only 9 for j in range ( 0 ,i): t + = 9 * pow ( 10 , j) # if the build number is # same as original number(n) if (n % power = = t): print (n,end = "") else : # observation print ((n - (n % power) - 1 ),end = "") else : print (n,end = "") # Driver Code if __name__ = = "__main__" : n = 1029 d = 102 # variable that stores no of digits in n num = dig(n) required_number(num, n, d) # this code is contributed by mits |
C#
// C# code to implement // above function using System; class GFG { // It's better to use long // to handle big integers // function to count no. of digits static long dig( long a) { long count = 0; while (a > 0) { a /= 10; count++; } return count; } // function to implement // above approach static void required_number( long num, long n, long d) { long i, j, power = 1, a, flag = 0; for (i = num; i >= 1; i--) { power = ( long )Math.Pow(10, i); a = n % power; // if difference between power // and n doesn't exceed d if (d > a) { flag = 1; break ; } } if (flag > 0) { long t = 0; // loop to build a number // from the appropriate no // of digits containing only 9 for (j = 0; j < i; j++) { t += ( long )(9 * Math.Pow(10, j)); } // if the build number is // same as original number(n) if (n % power == t) Console.Write( n); else { // observation Console.Write(n - (n % power) - 1); } } else Console.Write(n); } // Driver Code public static void Main() { long n = 1029, d = 102; // variable that stores // no. of digits in n long num = dig(n); required_number(num, n, d); } } // This code is contributed // by chandan_jnu |
PHP
<?php // PHP to implement above function // function to count no of digits function dig( $a ) { $count = 0; while ( $a > 0) { $a = (int)( $a / 10); $count ++; } return $count ; } // function to implement above approach function required_number( $num , $n , $d ) { $flag = 0; for ( $i = $num ; $i >= 1; $i --) { $power = pow(10, $i ); $a = $n % $power ; // if difference between power // and n doesn't exceed d if ( $d > $a ) { $flag = 1; break ; } } if ( $flag ) { $t = 0; // loop to build a number from the // appropriate no of digits containing only 9 for ( $j = 0; $j < $i ; $j ++) { $t += 9 * pow(10, $j ); } // if the build number is // same as original number(n) if ( $n % $power == $t ) echo $n ; else { // observation echo ( $n - ( $n % $power ) - 1); } } else echo $n ; } // Driver Code $n = 1029; $d = 102; // variable that stores no of // digits in n $num = dig( $n ); required_number( $num , $n , $d ); // This code is contributed by mits ?> |
Javascript
<script> // javascript code to implement above function // It's better to use var // to handle big integers // function to count no. of digits function dig(a) { var count = 0; while (a > 0) { a /= 10; count++; } return count; } // function to implement above approach function required_number(num , n , d) { var i, j, power=1, a, flag = 0; for (i = num; i >= 1; i--) { power = Math.pow(10, i); a = n % power; // if difference between power // and n doesn't exceed d if (d > a) { flag = 1; break ; } } if (flag>0) { var t = 0; // loop to build a number from the // appropriate no of digits containing // only 9 for (j = 0; j < i; j++) { t += 9 * Math.pow(10, j); } // if the build number is // same as original number(n) if (n % power == t) document.write( n); else { // observation document.write( n - (n % power) - 1); } } else document.write(n); } // Driver Code var n = 1029, d = 102; // variable that stores no // of digits in n var num = dig(n); required_number(num, n, d); // This code is contributed by 29AjayKumar </script> |
输出：
999
时间复杂性： O（位数）
另一种方法： 方法是将n减去变量num，即9 99 999，依此类推，然后除以temp，即1 10 100 1000，依此类推。如果在任何一点上n小于num，我们将中断并返回ans。对于每次迭代，我们计算一个值x作为（n-num）/temp，然后如果（x*temp）+num大于等于（n-d），这将是我们的ans，具有最多的9个，因为基本上我们将n减少一个因子，并添加num（可能的9个数），因为它是形式9 99 999，以此类推。
以下是上述方法的实施情况：
C++
#include <bits/stdc++.h> using namespace std; int maxPossible9s( int n, int d) { // initialising temp and ans variable to 1 int temp = 1; int ans = 1; int num = 0; // taking a condition which always holds true while ( true ) { // condition to break if (n < num) { break ; } else { // x is a factor by which we can calculate the // most number of 9s and then adding the most // number of 9s int x = (n - num) / temp; // if the condition is true then our ans will be // the value (x * temp + num) because num is of // the format 9 99 999 so on and hence gives the // most number of 9s if (x * temp + num >= (n - d)) { ans = x * temp + num; } // temp will be of the format 1 10 100 1000 // 10000 and so on temp *= 10; // num will be of the format 9 99 999 9999 and // so on num = num * 10 + 9; } } return ans; } int main() { int n = 1029; int d = 102; cout << maxPossible9s(n, d) << endl; } |
输出：
999
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
