Given a positive integer N, the task is to find the minimum N-digit number such that performing the following operations on it in the following order results into the largest N-digit number:
- Convert the number to its Binary Coded Decimal form.
- Concatenate all the resulting nibbles to form a binary number.
- Remove the least significant N bits from the number.
- Convert this obtained binary number to its decimal form.
Examples:
Input: N = 4
Output: 9990
Explanation:
Largest 4 digit number = 9999
BCD of 9999 = 1001 1001 1001 1001
Binary form = 1001100110011001
Replacing last 4 bits by 0000: 1001 1001 1001 0000 = 9990
Therefore, the minimum N-digit number that can generate 9999 is 9990Input: N = 5
Output: 99980
Explanation:
Largest 5 digit number = 99999
BCD of 99999 = 1001 1001 1001 1001 1001
Binary for = 10011001100110011001
Replacing last 5 bits by 00000: 10011001100110000000 = 99980
Therefore, the minimum N-digit number that can generate 99999 is 99980
Approach: The problem can be solved based on the following observations of BCD numbers. Follow the steps below to solve the problem:
- Each nibble in BCD does not increase beyond 1001 which is 9 in binary form, since the maximum single digit decimal number is 9.
- Thus, it can be concluded that the maximum binary number that can be obtained by bringing N nibbles together is 1001 concatenated N times, whose decimal representation is have to be the digit 9 concatenated N times.
- The last N LSBs from this binary form is required to be removed. Thus the values of these bits will not contribute in making the result larger. Therefore, keeping the last N bits as 9 is not necessary as we need the minimum number producing the maximum result.
- The value of floor(N/4) will give us the number of nibbles that will be completely removed from the number. Assign these nibbles the value of 0000 to minimize the number.
- The remainder of N/4 gives us the number of digits that would be switched to 0 from the LSB of the last non-zero nibble after having performed the previous step.
- This BCD formed by performing the above steps, when converted to decimal, generates the required maximized N digit number.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;void maximizedNdigit(int n){ int count0s, count9s; // If n is divisible by 4 if (n % 4 == 0) { count0s = n / 4; count9s = n - n / 4; } // Otherwise else { count0s = n / 4 + 1; count9s = n - count0s; count0s--; } while (count9s--) cout << '9'; if (n % 4 != 0) cout << '8'; while (count0s--) cout << '0'; cout << endl;}// Driver Codeint main(){ int n = 5; maximizedNdigit(n);} |
C
#include <stdio.h>void maximizedNdigit(int n){ int count0s, count9s; // If n is divisible by 4 if (n % 4 == 0) { count0s = n / 4; count9s = n - n / 4; } // Otherwise else { count0s = n / 4 + 1; count9s = n - count0s; count0s--; } while (count9s--) printf("9"); if (n % 4 != 0) printf("8"); while (count0s--) printf("0"); printf("\n");}// Driver Codeint main(){ int n = 5; maximizedNdigit(n); return 0;}// This code is contributed by phalashi. |
Java
// Java program to implement// the above approachimport java.io.*;class GFG{static void maximizedNdigit(int n) { int count0s, count9s; // If n is divisible by 4 if (n % 4 == 0) { count0s = n / 4; count9s = n - n / 4; } // Otherwise else { count0s = n / 4 + 1; count9s = n - count0s; count0s--; } while (count9s != 0) { count9s--; System.out.print('9'); } if (n % 4 != 0) System.out.print('8'); while (count0s != 0) { count0s--; System.out.print('0'); } System.out.println(); } // Driver Code public static void main(String[] args){ int n = 5; maximizedNdigit(n); } }// This code is contributed by sanjoy_62 |
Python3
# Python3 program to implement# the above approachdef maximizedNdigit(n): # If n is divisible by 4 if (n % 4 == 0): count0s = n // 4 count9s = n - n // 4 # Otherwise else: count0s = n // 4 + 1 count9s = n - count0s count0s -= 1 while (count9s): print('9', end = "") count9s -= 1 if (n % 4 != 0): print('8', end = "") while (count0s): print('0', end = "") count0s -= 1 print()# Driver Codeif __name__ == "__main__": n = 5 maximizedNdigit(n)# This code is contributed by chitranayal |
C#
// C# program to implement // the above approach using System;class GFG{static void maximizedNdigit(int n) { int count0s, count9s; // If n is divisible by 4 if (n % 4 == 0) { count0s = n / 4; count9s = n - n / 4; } // Otherwise else { count0s = n / 4 + 1; count9s = n - count0s; count0s--; } while (count9s != 0) { count9s--; Console.Write('9'); } if (n % 4 != 0) Console.Write('8'); while (count0s != 0) { count0s--; Console.Write('0'); } Console.WriteLine(); } // Driver Code public static void Main(){ int n = 5; maximizedNdigit(n); } }// This code is contributed by sanjoy_62 |
Javascript
<script>// JavaScript Program to implement// the above approachfunction maximizedNdigit(n){ let count0s, count9s; // If n is divisible by 4 if (n % 4 == 0) { count0s = Math.floor(n / 4); count9s = n - Math.floor(n / 4); } // Otherwise else { count0s = Math.floor(n / 4) + 1; count9s = n - count0s; count0s--; } while (count9s--) document.write('9'); if (n % 4 != 0) document.write('8'); while (count0s--) document.write('0'); document.write("<br>");}// Driver Code let n = 5; maximizedNdigit(n);// This code is contributed by Surbhi Tyagi.</script> |
Output:
99980
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
… [Trackback]
[…] Information to that Topic: geeksforgeeks.org/minimum-n-digit-number-required-to-obtain-largest-n-digit-number-after-performing-given-operations/ […]