Dado un número N , la tarea es imprimir los primeros N Números escalonados .
Un número se llama número de paso si todos los dígitos adyacentes tienen una diferencia absoluta de 1. Por ejemplo, 321 es un número de paso mientras que 421 no lo es.
Ejemplos:
Entrada: N = 7
Salida: 1, 2, 3, 4, 5, 6, 7
Entrada: N = 14
Salida: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 , 21, 22
Enfoque ingenuo: podemos comenzar desde 1 y verificar cada número, ya sea que sea un número de paso o no, y continuar hasta que encontremos el número de paso K-th.
Enfoque eficiente:
- Genere todos los números de pasos posibles hasta 1000 , para facilitar el cálculo
- Para cada valor de N, simplemente imprima el N ya calculado Números de paso
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to print first N
// Stepping numbers
#include <bits/stdc++.h>
using namespace std;
// Function to generate
// the Stepping numbers
void generateSteppingNos(
int x, set<int>& s)
{
if (x > 1e8)
return;
// Inserting the current
// element in the set
s.insert(x);
// Retrieving the last digit
// of the current number
int last = x % 10;
if (last - 1 >= 0)
// Appending x-1 to
// the current number
generateSteppingNos(
x * 10 + last - 1,
s);
// Appending x to
// the current number
generateSteppingNos(
x * 10 + last,
s);
if (last + 1 <= 9)
// Appending x+1 to
// the current number
generateSteppingNos(
x * 10 + last + 1,
s);
}
// Function to print
// N Stepping numbers
void NSteppingNumbers(int N)
{
set<int> s;
for (int i = 1; i <= 9; i++)
generateSteppingNos(i, s);
int count = 1;
// Printing N numbers from s
for (auto& it : s) {
if (count <= N) {
cout << it << ", ";
count++;
}
else
break;
}
}
// Driver code
int main()
{
int N = 14;
NSteppingNumbers(N);
return 0;
}
Java
// Java Program to print first N
// Stepping numbers
import java.util.*;
public class GFG
{
static HashSet<Integer> s = new HashSet<Integer>();
// Function to generate
// the Stepping numbers
static void generateSteppingNos(int x)
{
if (x > 1e8)
return;
// Inserting the current
// element in the set
s.add(x);
// Retrieving the last digit
// of the current number
int last = x % 10;
if (last - 1 >= 0)
// Appending x-1 to
// the current number
generateSteppingNos(x * 10 + last - 1);
// Appending x to
// the current number
generateSteppingNos(x * 10 + last);
if (last + 1 <= 9)
// Appending x+1 to
// the current number
generateSteppingNos(x * 10 + last + 1);
}
// Function to print
// N Stepping numbers
static void NSteppingNumbers(int N)
{
HashSet<Integer> s = new HashSet<Integer>();
int[] arr = {10, 11, 12, 21, 22};
for (int i = 1; i <= 9; i++)
{
generateSteppingNos(i);
s.add(i);
}
for(int i = 0; i < arr.length; i++)
{
s.add(arr[i]);
}
int count = 1;
// Printing N numbers from s
for(int it : s)
{
if (count <= N) {
System.out.print(it + ", ");
count++;
}
else
break;
}
}
public static void main(String[] args) {
int N = 14;
NSteppingNumbers(N);
}
}
// This code is contributed by mukesh07.
Python3
# Python3 Program to print first N # Stepping numbers # Function to generate # the Stepping numbers def generateSteppingNos(x, s): if (x > 1e8): return # Inserting the current # element in the set s.add(x) # Retrieving the last digit # of the current number last = x % 10 if (last - 1 >= 0): # Appending x-1 to # the current number generateSteppingNos(x * 10 + last - 1, s) # Appending x to # the current number generateSteppingNos(x * 10 + last, s) if (last + 1 <= 9): # Appending x+1 to # the current number generateSteppingNos(x * 10 + last + 1, s) # Function to print # N Stepping numbers def NSteppingNumbers(N): s = set() for i in range(1, 10): generateSteppingNos(i, s) count = 1 s.pop() # Printing N numbers from s for value in s: if (count <= N): print(value, end=', ') count = count + 1 else: break # Driver code N = 14 NSteppingNumbers(N) # This code is contributed by Sanjit_Prasad
C#
// C# Program to print first N
// Stepping numbers
using System;
using System.Collections.Generic;
class GFG {
static HashSet<int> s = new HashSet<int>();
// Function to generate
// the Stepping numbers
static void generateSteppingNos(int x)
{
if (x > 1e8)
return;
// Inserting the current
// element in the set
s.Add(x);
// Retrieving the last digit
// of the current number
int last = x % 10;
if (last - 1 >= 0)
// Appending x-1 to
// the current number
generateSteppingNos(x * 10 + last - 1);
// Appending x to
// the current number
generateSteppingNos(x * 10 + last);
if (last + 1 <= 9)
// Appending x+1 to
// the current number
generateSteppingNos(x * 10 + last + 1);
}
// Function to print
// N Stepping numbers
static void NSteppingNumbers(int N)
{
HashSet<int> s = new HashSet<int>();
int[] arr = {10, 11, 12, 21, 22};
for (int i = 1; i <= 9; i++)
{
generateSteppingNos(i);
s.Add(i);
}
for(int i = 0; i < arr.Length; i++)
{
s.Add(arr[i]);
}
int count = 1;
// Printing N numbers from s
foreach(int it in s)
{
if (count <= N) {
Console.Write(it + ", ");
count++;
}
else
break;
}
}
static void Main() {
int N = 14;
NSteppingNumbers(N);
}
}
// This code is contributed by suresh07.
Producción:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 21, 22,
Publicación traducida automáticamente
Artículo escrito por aqibmahboob1999 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA