Generating numbers using a given set of digits is a common problem in Java programming.It helps in understanding recursion, permutations, loops, and number construction logic.
- Given a array of digits (0-9)
- Given a required length N
- Generate all possible numbers of length N using the given digits
Example:
Input: Digits = {1, 2, 3}, N = 2
Output: 11, 12, 13, 21, 22, 23, 31, 32, 33
Approach 1: Using Recursion
This approach generates numbers recursively by constructing them one digit at a time until the required length is reached.
- Build numbers digit by digit.
- At each step, append one digit from the given set.
- Stop when the required length is reached.
public class GFG {
public static void generate(int[] digits, int length, String current) {
// Base case
if (current.length() == length) {
System.out.print(current + " ");
return;
}
// Recursive case
for (int digit : digits) {
generate(digits, length, current + digit);
}
}
public static void main(String[] args) {
int[] digits = { 1, 2, 3 };
int length = 2;
// Start generating numbers with an empty string
generate(digits, length, "");
}
}
Output
11 12 13 21 22 23 31 32 33
- Time Complexity: O(D^N) where D is the number of digits in the array and N is the required length of the numbers.
- Space Complexity: O(N) due to the recursion stack and the temporary string used to build each number.
Approach 2: Using Iteration
This approach works well for small values of N.
public class GFG {
public static void main(String[] args)
{
int[] digits = { 1, 2, 3 };
//Generate all numbers of length 2 using nested loops
for (int i : digits) {
for (int j : digits) {
System.out.print("" + i + j + " ");
}
}
}
}
Output
11 12 13 21 22 23 31 32 33
- Time Complexity: O(D^N) where D is the number of digits in the array and N is the required length of the numbers.
- Space Complexity: O(1) since no recursion or extra data structures are used.
Approach 3: Optimal Solution Using a Queue
The queue-based approach can be implemented step by step as follows:
- Initialize a queue and add all given digits as strings.
- While the required number of elements is not generated:
- Dequeue the front element from the queue.
- If its length equals the target length, print or store the number.
- Otherwise, for each digit in the set, append the digit to the current number and enqueue it back.
- Repeat the process until all numbers of the desired length are generated.
- This ensures numbers are generated in lexicographic (increasing) order efficiently.
import java.util.LinkedList;
import java.util.Queue;
public class GenerateNumbersQueue {
// Generate numbers of given length using digits
public static void generateNumbers(int[] digits, int length) {
Queue<String> queue = new LinkedList<>();
// Initialize the queue with single-digit numbers
for (int digit : digits) {
queue.add(String.valueOf(digit));
}
int count = 0;
int totalNumbers = (int) Math.pow(digits.length, length);
// Generate numbers using BFS-like approach
while (count < totalNumbers) {
String current = queue.poll();
if (current.length() == length) {
System.out.print(current + " ");
count++;
} else {
// Append each digit to current number and add back to queue
for (int digit : digits) {
queue.add(current + digit);
}
}
}
}
public static void main(String[] args) {
int[] digits = { 1, 2, 3 };
int length = 2;
generateNumbers(digits, length);
}
}
Output
11 12 13 21 22 23 31 32 33
- Time Complexity: O(D^N) where D is the number of digits in the array and N is the required length of the numbers.
- Space Complexity: O(D^N) to store partial numbers in the queue during generation.