Cuente números únicos que se pueden generar a partir de N agregando uno y eliminando ceros finales

Dado un número N. Agregue uno al número en el primer paso y si el número tiene ceros al final, elimine todos los ceros al final en el segundo paso. Continúe el proceso para el siguiente número generado. La tarea es contar la cantidad de números únicos que se pueden generar a partir de estas operaciones. 
Ejemplos: 
 

Entrada: N = 5 
Salida: 9 
5 -> 6 -> 7 -> 8 -> 9 -> 1 -> 2 -> 3 -> 4 -> 5 (se repite la misma secuencia) 
Tenga en cuenta que 10 no está incluido como contenía el cero final 
y la eliminación del cero dieron 1 como el siguiente elemento.
Entrada: N = 28 
Salida: 11 
 

Enfoque: El problema se puede resolver usando recursividad. Use un conjunto unordered_set para almacenar todos los números únicos. En caso de que se alcance un número dos veces, finalizamos la recursividad ya que se repetirá la misma secuencia y no obtendremos más números únicos. De lo contrario, inserte el número en el conjunto y, en el primer paso, aumente el número en 1 y elimine todos los ceros finales en el siguiente paso, si los hay.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the unique numbers
void count_unique(unordered_set<int>& s, int n)
{
 
    // If the number has
    // already been visited
    if (s.count(n))
        return;
 
    // Insert the number to the set
    s.insert(n);
 
    // First step
    n += 1;
 
    // Second step
    // remove trailing zeros
    while (n % 10 == 0) {
        n = n / 10;
    }
 
    // Recur again for the new number
    count_unique(s, n);
}
 
// Driver code
int main()
{
    int n = 10;
    unordered_set<int> s;
    count_unique(s, n);
 
    cout << s.size();
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
// Function to count the unique numbers
static void count_unique(HashSet<Integer>s, int n)
{
 
    // If the number has
    // already been visited
    if (s.contains(n))
        return;
 
    // Insert the number to the set
    s.add(n);
 
    // First step
    n += 1;
 
    // Second step
    // remove trailing zeros
    while (n % 10 == 0)
    {
        n = n / 10;
    }
 
    // Recur again for the new number
    count_unique(s, n);
}
 
// Driver code
public static void main(String[] args)
{
    int n = 10;
    HashSet<Integer>s = new HashSet<>();
    count_unique(s, n);
    System.out.println(s.size());
}
}
 
// This code has been contributed by 29AjayKumar

# Python3 implementation of the approach
 
# Function to count the unique numbers
def count_unique(s, n) :
 
    # If the number has
    # already been visited
    if (s.count(n)) :
        return;
 
    # Insert the number to the set
    s.append(n);
 
    # First step
    n += 1;
 
    # Second step
    # remove trailing zeros
    while (n % 10 == 0) :
        n = n // 10;
 
    # Recur again for the new number
    count_unique(s, n);
 
 
# Driver code
if __name__ == "__main__" :
 
    n = 10
    s = []
     
    count_unique(s, n)
     
    print(len(s))
 
# This code is contributed by Ryuga

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
// Function to count the unique numbers
static void count_unique(HashSet<int>s, int n)
{
 
    // If the number has
    // already been visited
    if (s.Contains(n))
        return;
 
    // Insert the number to the set
    s.Add(n);
 
    // First step
    n += 1;
 
    // Second step
    // remove trailing zeros
    while (n % 10 == 0)
    {
        n = n / 10;
    }
 
    // Recur again for the new number
    count_unique(s, n);
}
 
// Driver code
public static void Main(String[] args)
{
    int n = 10;
    HashSet<int>s = new HashSet<int>();
    count_unique(s, n);
    Console.WriteLine(s.Count);
}
}
 
// This code contributed by Rajput-Ji

<script>
 
// JavaScript implementation of the approach
 
// Function to count the unique numbers
function count_unique(s,n)
{
    // If the number has
    // already been visited
    if (s.has(n))
        return;
   
    // Insert the number to the set
    s.add(n);
   
    // First step
    n += 1;
   
    // Second step
    // remove trailing zeros
    while (n % 10 == 0)
    {
        n = Math.floor(n / 10);
    }
   
    // Recur again for the new number
    count_unique(s, n);
}
 
// Driver code
let n = 10;
let s = new Set();
count_unique(s, n);
document.write(s.size);
 
 
// This code is contributed by rag2127
 
</script>

19

Complejidad de tiempo: O(9*logN), como estamos usando la recursividad en el peor de los casos, llamaremos a la función 9 veces antes de disminuir N por división mínima de 10, lo que efectivamente costará el tiempo de logN.

Espacio auxiliar: O(9*logN), ya que estamos usando espacio extra para el conjunto.