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 numbersvoid 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 numbersvoid 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 codeint 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 digitsst = set()# Function to generate all possible numbersdef 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 numbersdef 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 codeif __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* 230)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
