Data Modelling & AI Data Structure & Algorithm

Minimum N-Digit number required to obtain largest N-digit number after performing given operations

23 June 2025

0

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 9990

Input: 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 Code
int 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 Code
int main()
{
  int n = 5;
  maximizedNdigit(n);
  return 0;
}
 
// This code is contributed by phalashi.

Java

// Java program to implement
// the above approach
import 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 approach
def 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 Code
if __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 approach
 
function 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:

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!

Minimum N-Digit number required to obtain largest N-digit number after performing given operations

C++

C

Java

Python3

C#

Javascript

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

How to Debug Slow Search Requests in Milvus

When Context Engineering Is Done Right, Hallucinations Can Be the Spark of AI Creativity

LEAVE A REPLY Cancel reply

Most Popular

I used the Google Pixel 10 Pro Fold and Galaxy Z Fold 7, and I’ve never been more conflicted

I wasn’t looking for a new app — but this one completely changed how I see daylight

It’s not sleek, it’s not cheap — but the Pixel 10 Pro Fold won me over anyway

Uh-oh, Pixel 10 users are still getting “fuzzy display” bug after Google’s fix

EDITOR PICKS

I used the Google Pixel 10 Pro Fold and Galaxy Z Fold 7, and I’ve never been more conflicted

I wasn’t looking for a new app — but this one completely changed how I see daylight

It’s not sleek, it’s not cheap — but the Pixel 10 Pro Fold won me over anyway

POPULAR POSTS

I used the Google Pixel 10 Pro Fold and Galaxy Z Fold 7, and I’ve never been more conflicted

I wasn’t looking for a new app — but this one completely changed how I see daylight

It’s not sleek, it’s not cheap — but the Pixel 10 Pro Fold won me over anyway

POPULAR CATEGORY

ABOUT US

FOLLOW US