Efficiently Generating Numbers with Given Digits in Java

 Problem: In Java, we are given a number 'N' and we have to generate and print the first 'N' numbers in increasing order using only digits 5 and 6.

For example, if N is 4, then we have to print 5, 6, 55 and 56.

Solution:

An inefficient solution would be to traverse through natural numbers and check if it contains only digits 5 and 6. If it does, we print the number and increment the count. Once the count becomes equal to N, we stop. However, this approach becomes inefficient for larger values of N, such as 10, as we would need to traverse through the first 566 natural numbers.

A more efficient solution would be to use a tree-like structure to generate the numbers. We know that the first two smallest numbers that can be formed using only 5 and 6 are 5 and 6. From these numbers, we can generate the next two numbers, which are 55 and 56. We can then use these four numbers to generate the next four numbers, which are 555, 556, 565, and 566. We can continue this process to generate the first N numbers.

We can achieve this without actually creating a tree structure by using a queue. We initialize the queue with 5 and 6, and then we perform a level order traversal by generating the nodes of the next level using the nodes of the current level. We then push these generated nodes to the queue, and we print the nodes from the front of the queue until we have printed N numbers.

To implement this solution in Java, we can use a Queue data structure and a loop. In the loop, we initialize the queue with 5 and 6, and then we pop a node from the front of the queue and print it. We then generate the nodes of the next level by appending 5 and 6 to the popped node, and we push these generated nodes to the back of the queue. We repeat this process until we have printed N numbers.

Here is an example Java code that implements this solution:

java
import java.util.*;

class GFG {
    
    static void printFirstN(int N)
    {
        Queue<String> q = new LinkedList<String>();
        
        q.add("5");
        q.add("6");
        
        for(int count =0; count<N; count++)
        {
            String curr = q.poll();
            System.out.print(curr + " ");
            
            q.add(curr + "5");
            q.add(curr + "6");
        }
    }
    
    public static void main (String[] args) {
        
        int n = 10;
        
        printFirstN(10);
    }
}

Output:
5 6 55 56 65 66 555 556 565 566

This code has a time complexity of O(N) and an auxiliary space complexity of O(N).