Given an integer N. The following tasks are performed:
- The number is noted.
- The leading digit from N is subtracted from N and the resulting value is stored back in N.
- The new value of N is again noted.
- This process is continued till N becomes 0. Finally, 0 is noted down in the end.
For example, take N = 13. The numbers noted down in the process of reducing 13 to 0 will be:
- 13
- 13 – 1 = 12
- 12 – 1 = 11
- 11 – 1 = 10
- 10 – 1 = 9
- 9 – 9 = 0
Given an integer K, which is the total count of numbers noted down in the process of reducing a number N to 0 as described above, the task is to find the largest possible value of the starting number N.
Examples:
Input: k = 2
Output: 9
Explanation: Numbers noted = {9}
- Subtract Leading digit: 9 – 9 = 0. Numbers noted = {9, 0}
Input: k = 3
Output: 10
Explanation: Numbers noted = {10}
- Subtract Leading digit: 10 – 1 = 9. Numbers noted = {10, 9}
- Subtract Leading digit: 9 – 9 = 0. Numbers noted = {10, 9, 0}
Approach: The idea is to observe that the maximum possible value of N will always be less than 10*K. Therefore, the idea is to apply binary search in the range K to 10*K and to look for the greatest number which can be reduced to 0 in K steps.
To find the largest possible number:
- Initialize left to k and right to k*10.
- Initialize mid to (left + right) / 2.
- Get the count of the number noted down to convert mid to 0 and store it in len.
- Follow divide and conquer approach: While len is not equal to k:
- Update the mid to the current (left + right) / 2.
- Get the count when starting with mid.
- If the count is greater than mid, update right to mid.
- Else, update left to mid.
- Now, mid has one value which will result in k integers written down.
- To find the largest such number:
- While the count is equal to k:
- If the current count is not equal to the count got by taking mid+1, break
- Else, keep incrementing mid by 1.
- mid is now the largest possible integer if k integers are written down.
Below is the implementation of the above approach:
C++
// C++ program to implement above approach#include <bits/stdc++.h>using namespace std;// Utility function to return the first// digit of a number.int firstDigit(int n){ // Remove last digit from number // till only one digit is left while (n >= 10) { n /= 10; } // return the first digit return n;}// Utility function that returns the count of numbers// written down when starting from nint getCount(int n){ int count = 1; while (n != 0) { int leadDigit = firstDigit(n); n -= leadDigit; count++; } return count;}// Function to find the largest number N which// can be reduced to 0 in K stepsint getLargestNumber(int k){ int left = k; int right = k * 10; int mid = (left + right) / 2; // Get the sequence length of the mid point int len = getCount(mid); // Until k sequence length is reached while (len != k) { // Update mid point mid = (left + right) / 2; // Get count of the new mid point len = getCount(mid); if (len > k) { // Update right to mid right = mid; } else { // Update left to mid left = mid; } } // Increment mid point by one while count // is equal to k to get the maximum value // of mid point while (len == k) { if (len != getCount(mid + 1)) { break; } mid++; } return (mid);}// Driver Codeint main(){ int k = 3; cout << getLargestNumber(k); return 0;} |
Java
// Java program to implement above approachimport java.io.*;class GFG{ // Utility function to return the first// digit of a number.static int firstDigit(int n){ // Remove last digit from number // till only one digit is left while (n >= 10) { n /= 10; } // return the first digit return n;}// Utility function that returns the count of numbers// written down when starting from nstatic int getCount(int n){ int count = 1; while (n != 0) { int leadDigit = firstDigit(n); n -= leadDigit; count++; } return count;}// Function to find the largest number N which// can be reduced to 0 in K stepsstatic int getLargestNumber(int k){ int left = k; int right = k * 10; int mid = (left + right) / 2; // Get the sequence length of the mid point int len = getCount(mid); // Until k sequence length is reached while (len != k) { // Update mid point mid = (left + right) / 2; // Get count of the new mid point len = getCount(mid); if (len > k) { // Update right to mid right = mid; } else { // Update left to mid left = mid; } } // Increment mid point by one while count // is equal to k to get the maximum value // of mid point while (len == k) { if (len != getCount(mid + 1)) { break; } mid++; } return (mid);} // Driver Code public static void main (String[] args) { int k = 3; System.out.println (getLargestNumber(k)); }}// This code is contributed by jit_t |
Python3
# Python3 program to implement above approach# Utility function to return the first# digit of a number.def firstDigit(n) : # Remove last digit from number # till only one digit is left while (n >= 10) : n //= 10; # return the first digit return n;# Utility function that returns # the count of numbers written # down when starting from ndef getCount(n) : count = 1; while (n != 0) : leadDigit = firstDigit(n); n -= leadDigit; count += 1; return count;# Function to find the largest number N # which can be reduced to 0 in K stepsdef getLargestNumber(k) : left = k; right = k * 10; mid = (left + right) // 2; # Get the sequence length of the mid point length = getCount(mid); # Until k sequence length is reached while (length != k) : # Update mid point mid = (left + right) // 2; # Get count of the new mid point length = getCount(mid); if (length > k) : # Update right to mid right = mid; else : # Update left to mid left = mid; # Increment mid point by one while count # is equal to k to get the maximum value # of mid point while (length == k) : if (length != getCount(mid + 1)) : break; mid += 1; return mid;# Driver Codeif __name__ == "__main__" : k = 3; print(getLargestNumber(k));# This code is contributed by Ryuga |
C#
// C# implementation of the approach using System;class GFG{// Utility function to return the first // digit of a number. static int firstDigit(int n) { // Remove last digit from number // till only one digit is left while (n >= 10) { n /= 10; } // return the first digit return n; } // Utility function that returns the count of numbers // written down when starting from n static int getCount(int n) { int count = 1; while (n != 0) { int leadDigit = firstDigit(n); n -= leadDigit; count++; } return count; } // Function to find the largest number N which // can be reduced to 0 in K steps static int getLargestNumber(int k) { int left = k; int right = k * 10; int mid = (left + right) / 2; // Get the sequence length of the mid point int len = getCount(mid); // Until k sequence length is reached while (len != k) { // Update mid point mid = (left + right) / 2; // Get count of the new mid point len = getCount(mid); if (len > k) { // Update right to mid right = mid; } else { // Update left to mid left = mid; } } // Increment mid point by one while count // is equal to k to get the maximum value // of mid point while (len == k) { if (len != getCount(mid + 1)) { break; } mid++; } return (mid); } // Driver Code public static void Main(String []args) { int k = 3; Console.WriteLine( getLargestNumber(k)); } }// This code is contributed by Arnab Kundu |
Javascript
<script> // Javascript implementation of the approach // Utility function to return the first // digit of a number. function firstDigit(n) { // Remove last digit from number // till only one digit is left while (n >= 10) { n = parseInt(n / 10, 10); } // return the first digit return n; } // Utility function that returns the count of numbers // written down when starting from n function getCount(n) { let count = 1; while (n != 0) { let leadDigit = firstDigit(n); n -= leadDigit; count++; } return count; } // Function to find the largest number N which // can be reduced to 0 in K steps function getLargestNumber(k) { let left = k; let right = k * 10; let mid = parseInt((left + right) / 2, 10); // Get the sequence length of the mid point let len = getCount(mid); // Until k sequence length is reached while (len != k) { // Update mid point mid = parseInt((left + right) / 2, 10); // Get count of the new mid point len = getCount(mid); if (len > k) { // Update right to mid right = mid; } else { // Update left to mid left = mid; } } // Increment mid point by one while count // is equal to k to get the maximum value // of mid point while (len == k) { if (len != getCount(mid + 1)) { break; } mid++; } return (mid); } let k = 3; document.write( getLargestNumber(k)); </script> |
PHP
<?php// PHP program to implement above approach// Utility function to return the // first digit of a number.function firstDigit($n){ // Remove last digit from number // till only one digit is left while ($n >= 10) { $n = (int)($n / 10); } // return the first digit return $n;}// Utility function that returns the // count of numbers written down when // starting from nfunction getCount($n){ $count = 1; while ($n != 0) { $leadDigit = firstDigit($n); $n -= $leadDigit; $count++; } return $count;}// Function to find the largest number N // which can be reduced to 0 in K stepsfunction getLargestNumber($k){ $left = $k; $right = $k * 10; $mid = (int)(($left + $right) / 2); // Get the sequence length // of the mid point $len = getCount($mid); // Until k sequence length is reached while ($len != $k) { // Update mid point $mid = (int)(($left + $right) / 2); // Get count of the new mid point $len = getCount($mid); if ($len > $k) { // Update right to mid $right = $mid; } else { // Update left to mid $left = $mid; } } // Increment mid point by one while count // is equal to k to get the maximum value // of mid point while ($len == $k) { if ($len != getCount($mid + 1)) { break; } $mid++; } return ($mid);}// Driver Code$k = 3;echo(getLargestNumber($k));// This code is contributed by Code_Mech.?> |
Output
10
Another Approach:
1. We use binary search to find the largest number N which can be reduced to 0 in K steps.
2. We set lo to 1 and hi to 1000000, which is an arbitrary upper bound for N.
3. In each iteration of the binary search, we compute the sum of the first K+1 terms of the geometric series with ratio mid and first term 1. 4. If this sum is greater than 1000000000 (which is the maximum possible value of sum), or if it exceeds mid * (K+1), we update hi to mid – 1, otherwise we update lo to mid.
5. The value of mid is computed as (lo + hi + 1) / 2 to ensure that we always round up.
6. We use long long to avoid integer overflow when computing the sum of the geometric series.
7. Finally, we return lo as the largest number N which can be reduced to 0 in K steps.
C++
#include <iostream>using namespace std;int largest_number(int k){ int lo = 1, hi = 1000000; while (lo < hi) { int mid = (lo + hi + 1) / 2; long long sum = 0, term = 1; for (int i = 0; i <= k; i++) { sum += term; term *= mid; if (sum > 1000000000LL) break; // avoid overflow } if (sum > 1000000000LL || sum > (long long)mid * (k + 1)) { hi = mid - 1; } else { lo = mid; } } return lo;}int main(){ int k = 10; int N = largest_number(k); cout << "The largest number N which can be reduced to " "0 in " << k << " steps is " << N << endl; return 0;}// This code is contributed by shivhack999 |
C
#include <stdio.h>int largest_number(int k){ int lo = 1, hi = 1000000; while (lo < hi) { int mid = (lo + hi + 1) / 2; long long sum = 0, term = 1; for (int i = 0; i <= k; i++) { sum += term; term *= mid; if (sum > 1000000000LL) break; // avoid overflow } if (sum > 1000000000LL || sum > (long long)mid * (k + 1)) { hi = mid - 1; } else { lo = mid; } } return lo;}int main(){ int k = 10; int N = largest_number(k); printf("The largest number N which can be reduced to 0 " "in %d steps is %d\n", k, N); return 0;} |
Java
import java.util.*;public class Main { public static int largest_number(int k) { // Binary search for the largest number N which can // be reduced to 0 in k steps int lo = 1, hi = 1000000; while (lo < hi) { int mid = (lo + hi + 1) / 2; long sum = 0, term = 1; for (int i = 0; i <= k; i++) { sum += term; term *= mid; if (sum > 1000000000L) break; // avoid overflow } if (sum > 1000000000L || sum > (long)mid * (k + 1)) { hi = mid - 1; } else { lo = mid; } } return lo; } public static void main(String[] args) { int k = 10; int N = largest_number(k); System.out.println( "The largest number N which can be reduced to " + "0 in " + k + " steps is " + N); }} |
Python3
def largest_number(k): # Initialize the lower and upper bounds lo = 1 hi = 1000000 # Binary search for the largest number N which can be reduced to 0 in k steps while lo < hi: mid = (lo + hi + 1) // 2 sum = 0 term = 1 # Calculate the sum of the geometric series up to k+1 terms for i in range(k + 1): sum += term term *= mid # Avoid overflow if sum > 1000000000: break # If the sum exceeds 10^9 or N is too small, search in the upper half if sum > 1000000000 or sum > mid * (k + 1): hi = mid - 1 # Otherwise, search in the lower half else: lo = mid return lok = 10N = largest_number(k)print(f"The largest number N which can be reduced to 0 in {k} steps is {N}") |
C#
using System;public class MainClass { public static int LargestNumber(int k) { // Binary search for the largest number N which can // be reduced to 0 in k steps int lo = 1, hi = 1000000; while (lo < hi) { int mid = (lo + hi + 1) / 2; long sum = 0, term = 1; for (int i = 0; i <= k; i++) { sum += term; term *= mid; if (sum > 1000000000L) break; // avoid overflow } if (sum > 1000000000L || sum > (long)mid * (k + 1)) { hi = mid - 1; } else { lo = mid; } } return lo; } public static void Main(string[] args) { int k = 10; int N = LargestNumber(k); Console.WriteLine( "The largest number N which can be reduced to 0 in " + k + " steps is " + N); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
function largestNumber(k) { // Initialize the lower and upper bounds let lo = 1; let hi = 1000000; // Binary search for the largest number N which can be reduced to 0 in k steps while (lo < hi) { let mid = Math.floor((lo + hi + 1) / 2); let sum = 0; let term = 1; // Calculate the sum of the geometric series up to k+1 terms for (let i = 0; i <= k; i++) { sum += term; term *= mid; // Avoid overflow if (sum > 1000000000) { break; } } // If the sum exceeds 10^9 or N is too small, search in the upper half if (sum > 1000000000 || sum > mid * (k + 1)) { hi = mid - 1; } else { // Otherwise, search in the lower half lo = mid; } } return lo;}const k = 10;const N = largestNumber(k);console.log(`The largest number N which can be reduced to 0 in ${k} steps is ${N}`); |
Output
The largest number N which can be reduced to 0 in 10 steps is 1
Time complexity of the largest_number function is O(k log N), where N is the largest number that can be reduced to 0 in k steps. This is because of the binary search which has a time complexity of O(log N), and for each iteration of the binary search, we compute the sum of the geometric series up to k+1 terms, which has a time complexity of O(k). Since we perform the binary search until we converge on a single value, the total time complexity is O(k log N).
The space complexity of the function is O(1) because we only use a fixed number of integer variables regardless of the size of N.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
