Print all numbers less than N with at-most 2 unique digits

0 0 5 minutes read

Given a number N(less than 10^9). The task is to print all the numbers less than N which are having a maximum of 2 unique digits.
Note: Number such as 100, 111, 101 are valid as the number of unique digits are at most 2 but 123 is invalid as it has 3 unique digits.
Examples:

Input: N = 12
Output: The numbers are: 1 2 3 4 5 6 7 8 9 10 11
Input: N = 154
Output: The numbers are: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 110 111 112 113 114 115 116 117 118 119 121 122 131 133 141 144 151

Approach:

Since we are said a maximum of two unique digits, two loops will give us all combination of two digits.
A recursive function is written in terms to generate all the numbers using two digits.
Call the function with num initially as 0, and generate numbers using recurrence num*10+a and num*10+b, with the base case being num>=n.
A set can be used to store all the numbers as there can be duplicate elements which the recursion function generates.

Below is the implementation of the above approach:

C++

// C++ program to print all the numbers
// less than N which have at most 2 unique digits
#include <bits/stdc++.h>
using namespace std;
 
set<int> st;
 
// Function to generate all possible numbers
void generateNumbers(int n, int num, int a, int b)
{
    // If the number is less than n
    if (num > 0 && num < n)
        st.insert(num);
 
    // If the number exceeds
    if (num >= n)
        return;
 
    // Check if it is not the same number
    if (num * 10 + a > num)
        generateNumbers(n, num * 10 + a, a, b);
 
    generateNumbers(n, num * 10 + b, a, b);
}
 
// Function to print all numbers
void printNumbers(int n)
{
    // All combination of digits
    for (int i = 0; i <= 9; i++)
        for (int j = i + 1; j <= 9; j++)
            generateNumbers(n, 0, i, j);
 
    cout << "The numbers are: ";
 
    // Print all numbers
    while (!st.empty()) {
        cout << *st.begin() << " ";
        st.erase(st.begin());
    }
}
 
// Driver code
int main()
{
    int n = 12;
 
    printNumbers(n);
 
    return 0;
}

Java

// Java program to print all the numbers 
// less than N which have at most 2 unique digits 
import java.util.*;
class GFG{
   
static Set<Integer> st= new HashSet<Integer>(); 
   
// Function to generate all possible numbers 
static void generateNumbers(int n, int num, int a, int b) 
{ 
    // If the number is less than n 
    if (num > 0 && num < n) 
        st.add(num); 
   
    // If the number exceeds 
    if (num >= n) 
        return; 
   
    // Check if it is not the same number 
    if (num * 10 + a > num) 
        generateNumbers(n, num * 10 + a, a, b); 
   
    generateNumbers(n, num * 10 + b, a, b); 
} 
   
// Function to print all numbers 
static void printNumbers(int n) 
{ 
    // All combination of digits 
    for (int i = 0; i <= 9; i++) 
        for (int j = i + 1; j <= 9; j++) 
            generateNumbers(n, 0, i, j); 
   
    System.out.print( "The numbers are: "); 
   
    // Print all numbers 
    System.out.print(st);
     
    st.clear();
} 
   
// Driver code 
public static void main(String args[]) 
{ 
    int n = 12; 
   
    printNumbers(n); 
   
} 
}
// This code is contributed by Arnab Kundu

Python3

# Python 3 program to print all the 
# numbers less than N which have at 
# most 2 unique digits
st = set()
 
# Function to generate all possible numbers
def generateNumbers(n, num, a, b):
     
    # If the number is less than n
    if (num > 0 and num < n):
        st.add(num)
 
    # If the number exceeds
    if (num >= n):
        return
 
    # Check if it is not the same number
    if (num * 10 + a > num):
        generateNumbers(n, num * 10 + a, a, b)
 
    generateNumbers(n, num * 10 + b, a, b)
 
# Function to print all numbers
def printNumbers(n):
     
    # All combination of digits
    for i in range(10):
        for j in range(i + 1, 10, 1):
            generateNumbers(n, 0, i, j)
 
    print("The numbers are:", end = " ")
     
    # Print all numbers
    l = list(st)
    for i in l:
        print(i, end = " ")
 
# Driver code
if __name__ == '__main__':
    n = 12
 
    printNumbers(n)
 
# This code is contributed by
# Shashank_Sharma

C#

// C# program to print all the numbers 
// less than N which have at most 2 unique digits 
using System;
using System.Collections.Generic;
 
class GFG
{
     
static SortedSet<int> st = new SortedSet<int>(); 
     
// Function to generate all possible numbers 
static void generateNumbers(int n, int num, int a, int b) 
{ 
    // If the number is less than n 
    if (num > 0 && num < n) 
        st.Add(num); 
     
    // If the number exceeds 
    if (num >= n) 
        return; 
     
    // Check if it is not the same number 
    if (num * 10 + a > num) 
        generateNumbers(n, num * 10 + a, a, b); 
     
    generateNumbers(n, num * 10 + b, a, b); 
} 
     
// Function to print all numbers 
static void printNumbers(int n) 
{ 
    // All combination of digits 
    for (int i = 0; i <= 9; i++) 
        for (int j = i + 1; j <= 9; j++) 
            generateNumbers(n, 0, i, j); 
     
    Console.Write( "The numbers are: "); 
     
    // Print all numbers 
    foreach(int obj in st)
        Console.Write(obj+" ");
     
    st.Clear();
} 
     
// Driver code 
public static void Main(String []args) 
{ 
    int n = 12; 
     
    printNumbers(n); 
} 
}
 
// This code has been contributed by 29AjayKumar

Javascript

<script>
// Javascript program to print all the numbers 
// less than N which have at most 2 unique digits 
 
let st= new Set();
 
// Function to generate all possible numbers 
function generateNumbers(n,num,a,b)
{
    // If the number is less than n 
    if (num > 0 && num < n) 
        st.add(num); 
     
    // If the number exceeds 
    if (num >= n) 
        return; 
     
    // Check if it is not the same number 
    if (num * 10 + a > num) 
        generateNumbers(n, num * 10 + a, a, b); 
     
    generateNumbers(n, num * 10 + b, a, b); 
}
 
// Function to print all numbers 
function printNumbers(n)
{
    // All combination of digits 
    for (let i = 0; i <= 9; i++) 
        for (let j = i + 1; j <= 9; j++) 
            generateNumbers(n, 0, i, j); 
     
    document.write( "The numbers are: "); 
     
    // Print all numbers 
    document.write(Array.from(st).sort(function(a,b){return a-b;}).join(" "));
       
    st.clear();
}
 
// Driver code 
let n = 12; 
 
printNumbers(n);
 
 
// This code is contributed by rag2127
</script>

Output:

The numbers are: 1 2 3 4 5 6 7 8 9 10 11

Time complexity: O(36* 2³⁰)
Space Complexity : 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 zambiatek!