Dado un número N (menos de 10^9). La tarea es imprimir todos los números menores que N que tengan un máximo de 2 dígitos únicos.
Nota : Números como 100, 111, 101 son válidos ya que la cantidad de dígitos únicos es como máximo 2, pero 123 no es válido ya que tiene 3 dígitos únicos.
Ejemplos:
Entrada : N = 12
Salida : Los números son: 1 2 3 4 5 6 7 8 9 10 11
Entrada : N = 154
Salida : Los números son: 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 44 45 46 47 48 49 50 51 52 53 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 112 113 114 115 116 117 118 119 121 122 131 141 144 151
Enfoque :
- Como se dice un máximo de dos dígitos únicos, dos bucles nos darán todas las combinaciones de dos dígitos.
- Una función recursiva se escribe en términos de generar todos los números usando dos dígitos.
- Llame a la función con num inicialmente como 0 y genere números usando la recurrencia num*10+a y num*10+b , siendo el caso base num>=n.
- Se puede usar un conjunto para almacenar todos los números, ya que puede haber elementos duplicados que genera la función de recursión.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
The numbers are: 1 2 3 4 5 6 7 8 9 10 11
Complejidad del tiempo: O(36* 2 30 )