Given two positive integers N and D, the task is to decrement the value of N by at most D such that N contains the maximum count of trailing 9s.
Examples:
Input: N = 1025, D = 6
Output: 1019
Explanation:
Decrementing N by 6 modifies N to 1019, which consists of maximum possible count of trailing 9s.
Therefore, the required output is 1019.Input: N = 1025, D = 5
Output: 1025
Decrementing N by all possible values up to D(= 5), no number can be obtained which contains trailing 9.
Therefore, the required output is 1025.
Naive Approach: The simplest approach to solve this problem is to iterate over the range [0, D] using variable i and decrement the value of N by i. Finally, print the value of N which contains the maximum possible count of trailing 9.
Time Complexity: O(D * log10(N))
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the following observations:
N % pow(10, i) gives the last i digits of N
Follow the steps below to solve the problem:
- Initialize a variable say, res to store the decremented value of N with maximum count of trailing 9.
- Initialize a variable say, cntDigits to store the count of digits in N.
- Iterate over the range [1, cntDigits] using variable i and check if N % pow(10, i) greater than or equal to D or not. If found to be true, then print the value of res.
- Otherwise, update res to N % pow(10, i) – 1.
Below is the implementation of the above approach:
C++
// CPP program for the above approach #include <bits/stdc++.h> #define ll long long int using namespace std; // Function to find a number with // maximum count of trailing nine void maxNumTrailNine(int n, int d) { int res = n; // Stores count of digits in n int cntDigits = log10(n) + 1; // Stores power of 10 int p10 = 10; for (int i = 1; i <= cntDigits; i++) { // If last i digits greater than // or equal to d if (n % p10 >= d) { break; } else { // Update res res = n - n % p10 - 1; } // Update p10 p10 = p10 * 10; } cout << res; } // Driver Code int main() { int n = 1025, d = 6; // Function Call maxNumTrailNine(n, d); } |
Java
// Java program for the above approach class GFG { // Function to find a number with // maximum count of trailing nine static void maxNumTrailNine(int n, int d) { int res = n; // Stores count of digits in n int cntDigits = (int)Math.log10(n) + 1; // Stores power of 10 int p10 = 10; for (int i = 1; i <= cntDigits; i++) { // If last i digits greater than // or equal to d if (n % p10 >= d) { break; } else { // Update res res = n - n % p10 - 1; } // Update p10 p10 = p10 * 10; } System.out.println(res); } // Driver Code public static void main (String[] args) { int n = 1025, d = 6; // Function Call maxNumTrailNine(n, d); } }// This code is contribute by AnkThon |
Python3
# Python3 program for the above approachfrom math import log10# Function to find a number with# maximum count of trailing ninedef maxNumTrailNine(n, d): res = n # Stores count of digits in n cntDigits = int(log10(n) + 1) # Stores power of 10 p10 = 10 for i in range(1, cntDigits + 1): # If last i digits greater than # or equal to d if (n % p10 >= d): break else: # Update res res = n - n % p10 - 1 # Update p10 p10 = p10 * 10 print (res)# Driver Codeif __name__ == '__main__': n, d = 1025, 6 # Function Call maxNumTrailNine(n, d) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System;class GFG { // Function to find a number with // maximum count of trailing nine static void maxNumTrailNine(int n, int d) { int res = n; // Stores count of digits in n int cntDigits = (int)Math.Log10(n) + 1; // Stores power of 10 int p10 = 10; for (int i = 1; i <= cntDigits; i++) { // If last i digits greater than // or equal to d if (n % p10 >= d) { break; } else { // Update res res = n - n % p10 - 1; } // Update p10 p10 = p10 * 10; } Console.WriteLine(res); } // Driver Code public static void Main(String[] args) { int n = 1025, d = 6; // Function Call maxNumTrailNine(n, d); } }// This code contributed by shikhasingrajput |
Javascript
<script>// Javascript program for the above approach // Function to find a number with // maximum count of trailing nine function maxNumTrailNine(n, d) { let res = n; // Stores count of digits in n let cntDigits = parseInt(Math.log(n) / Math.log(10)) + 1; // Stores power of 10 let p10 = 10; for(let i = 1; i <= cntDigits; i++) { // If last i digits greater than // or equal to d if (n % p10 >= d) { break; } else { // Update res res = n - n % p10 - 1; } // Update p10 p10 = p10 * 10; } document.write(res); } // Driver Code let n = 1025, d = 6; // Function Call maxNumTrailNine(n, d); // This code is contributed by souravmahato348</script> |
1019
Time Complexity: O(min(log10(D), log10(N))
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
