Encuentra el N-ésimo número positivo cuya raíz digital es X

Dado un número X ( 1<= X <= 9) y un número positivo N, encuentre el N-ésimo número positivo cuya raíz digital es X.
Raíz digital : La raíz digital de un número positivo se obtiene sumando iterativamente los dígitos de un número. En cada iteración, el número se reemplaza por la suma de su dígito y la iteración se detiene cuando el número se reduce a un número de un solo dígito. Este número de un solo dígito se conoce como la raíz digital. Por ejemplo, la raíz digital de 65 es 2, porque 6 + 5 = 11 y 1 + 1 = 2.

Ejemplos:  

Entrada : X = 3, N = 100 
Salida : 894 
El N-ésimo número cuya raíz numérica es X es 894

Entrada : X = 7, N = 43 
Salida : 385

Método simple : el método simple es comenzar desde 1 y calcular la raíz digital de cada número, siempre que nos encontremos con un número cuya raíz digital sea igual a X, aumentamos nuestro contador en 1. Detendremos nuestra búsqueda cuando nuestro contador sea igual a n

A continuación se muestra la implementación del enfoque anterior:  

// C++ program to find the N-th number whose
// digital root is X
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the digital root of
// a number
int findDigitalRoot(int num)
{
    int sum = INT_MAX, tempNum = num;
 
    while (sum >= 10) {
        sum = 0;
 
        while (tempNum > 0) {
            sum += tempNum % 10;
            tempNum /= 10;
        }
 
        tempNum = sum;
    }
 
    return sum;
}
 
// Function to find the Nth number with
// digital root as X
void findAnswer(int X, int N)
{
    // Counter variable to keep the
    // count of valid numbers
    int counter = 0;
 
    for (int i = 1; counter < N; ++i) {
 
        // Find digital root
        int digitalRoot = findDigitalRoot(i);
 
        // Check if is required answer or not
        if (digitalRoot == X) {
            ++counter;
        }
 
        // Print the answer if you have found it
        // and breakout of the loop
        if (counter == N) {
            cout << i;
 
            break;
        }
    }
}
 
// Driver Code
int main()
{
    int X = 1, N = 3;
 
    findAnswer(X, N);
 
    return 0;
}

// Java program to find the N-th number whose
// digital root is X
class GFG
{
 
// Function to find the digital root of
// a number
static int findDigitalRoot(int num)
{
    int sum = Integer.MAX_VALUE, tempNum = num;
 
    while (sum >= 10)
    {
        sum = 0;
 
        while (tempNum > 0)
        {
            sum += tempNum % 10;
            tempNum /= 10;
        }
 
        tempNum = sum;
    }
 
    return sum;
}
 
// Function to find the Nth number with
// digital root as X
static void findAnswer(int X, int N)
{
    // Counter variable to keep the
    // count of valid numbers
    int counter = 0;
 
    for (int i = 1; counter < N; ++i)
    {
 
        // Find digital root
        int digitalRoot = findDigitalRoot(i);
 
        // Check if is required answer or not
        if (digitalRoot == X)
        {
            ++counter;
        }
 
        // Print the answer if you have found it
        // and breakout of the loop
        if (counter == N)
        {
            System.out.print( i);
 
            break;
        }
    }
}
 
// Driver Code
public static void main(String args[])
{
    int X = 1, N = 3;
 
    findAnswer(X, N);
}
}
 
// This code is contributed by Arnab Kundu

# Python3 program to find the N-th number whose
# digital root is X
import sys
 
# Function to find the digital root of
# a number
def findDigitalRoot(num):
    sum = sys.maxsize;
    tempNum = num;
 
    while (sum >= 10):
        sum = 0;
 
        while (tempNum > 0):
            sum += tempNum % 10;
            tempNum //= 10;
 
        tempNum = sum;
 
    return sum;
 
# Function to find the Nth number with
# digital root as X
def findAnswer(X, N):
     
    # Counter variable to keep the
    # count of valid numbers
    counter = 0;
    i = 0;
    while (counter < N):
        i += 1;
         
        # Find digital root
        digitalRoot = findDigitalRoot(i);
         
        # Check if is required answer or not
        if (digitalRoot == X):
            counter += 1;
         
        # Print the answer if you have found it
        # and breakout of the loop
        if (counter == N):
            print(i);
            break;
 
# Driver Code
if __name__ == '__main__':
    X = 1;
    N = 3;
 
    findAnswer(X, N);
 
# This code is contributed by 29AjayKumar

// C# program to find the N-th number whose
// digital root is X
using System;
 
class GFG
{
 
// Function to find the digital root of
// a number
static int findDigitalRoot(int num)
{
    int sum = int.MaxValue, tempNum = num;
 
    while (sum >= 10)
    {
        sum = 0;
 
        while (tempNum > 0)
        {
            sum += tempNum % 10;
            tempNum /= 10;
        }
 
        tempNum = sum;
    }
 
    return sum;
}
 
// Function to find the Nth number with
// digital root as X
static void findAnswer(int X, int N)
{
    // Counter variable to keep the
    // count of valid numbers
    int counter = 0;
 
    for (int i = 1; counter < N; ++i)
    {
 
        // Find digital root
        int digitalRoot = findDigitalRoot(i);
 
        // Check if is required answer or not
        if (digitalRoot == X)
        {
            ++counter;
        }
 
        // Print the answer if you have found it
        // and breakout of the loop
        if (counter == N)
        {
            Console.Write( i);
 
            break;
        }
    }
}
 
// Driver Code
public static void Main(String []args)
{
    int X = 1, N = 3;
 
    findAnswer(X, N);
}
}
 
// This code has been contributed by 29AjayKumar

<?php
// PHP program to find the N-th number
// whose digital root is X
 
// Function to find the digital root
// of a number
function findDigitalRoot($num)
{
    $sum = PHP_INT_MAX;
    $tempNum = $num;
 
    while ($sum >= 10)
    {
        $sum = 0;
 
        while ($tempNum > 0)
        {
            $sum += $tempNum % 10;
            $tempNum /= 10;
        }
 
        $tempNum = $sum;
    }
 
    return $sum;
}
 
// Function to find the Nth number 
// with digital root as X
function findAnswer($X, $N)
{
     
    // Counter variable to keep the
    // count of valid numbers
    $counter = 0;
 
    for ($i = 1; $counter < $N; ++$i)
    {
 
        // Find digital root
        $digitalRoot = findDigitalRoot($i);
 
        // Check if is required answer or not
        if ($digitalRoot == $X)
        {
            ++$counter;
        }
 
        // Print the answer if you have found
        // it and breakout of the loop
        if ($counter == $N)
        {
            echo( $i);
 
            break;
        }
    }
}
 
// Driver Code
$X = 1; $N = 3;
 
findAnswer($X, $N);
 
// This code is contributed by Code_Mech.

<script>
 
// JavaScript program to find the N-th number whose
// digital root is X    
 
// Function to find the digital root of
// a number
    function findDigitalRoot(num) {
        var sum = Number.MAX_VALUE, tempNum = num;
 
        while (sum >= 10) {
            sum = 0;
 
            while (tempNum > 0) {
                sum += tempNum % 10;
                tempNum = parseInt(tempNum/10);
            }
 
            tempNum = sum;
        }
 
        return sum;
    }
 
    // Function to find the Nth number with
    // digital root as X
    function findAnswer(X , N) {
        // Counter variable to keep the
        // count of valid numbers
        var counter = 0;
 
        for (var i = 1; counter < N; ++i) {
 
            // Find digital root
            var digitalRoot = findDigitalRoot(i);
 
            // Check if is required answer or not
            if (digitalRoot == X) {
                counter+=1;
            }
 
            // Print the answer if you have found it
            // and breakout of the loop
            if (counter == N) {
                document.write(i);
 
                break;
            }
        }
    }
 
    // Driver Code
     
        var X = 1, N = 3;
 
        findAnswer(X, N);
 
// This code contributed by gauravrajput1
 
</script>

19

Enfoque eficiente: podemos encontrar la raíz digital de un número K directamente usando la fórmula: 

digitalRoot(k) = (k - 1)mod 9 +1

A partir de esto podemos encontrar el N-ésimo número cuya raíz digital es K como,  

Nth number = (N - 1)*9 + K

A continuación se muestra la implementación del enfoque anterior:  

// C++ program to find the N-th number with
// digital root as X
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the N-th number with
// digital root as X
int findAnswer(int X, int N)
{
    return (N - 1) * 9 + X;
}
 
// Driver Code
int main()
{
    int X = 7, N = 43;
 
    cout << findAnswer(X, N);
 
    return 0;
}

// Java program to find the N-th number with
// digital root as X
 
class GfG
{
 
    // Function to find the N-th number with
    // digital root as X
    static int findAnswer(int X, int N)
    {
        return (N - 1) * 9 + X;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int X = 7, N = 43;
        System.out.println(findAnswer(X, N));
    }
}
 
// This code contributed by Rajput-Ji

# Python3 program to find the N-th 
# number with digital root as X
 
# Function to find the N-th number
# with digital root as X
def findAnswer(X, N):
 
    return (N - 1) * 9 + X;
 
# Driver Code
X = 7;
N = 43;
print(findAnswer(X, N));
 
# This code is contributed by mits

// C# program to find the N-th number
// with digital root as X
using System;
 
class GFG
{
 
// Function to find the N-th
// number with digital root as X
static int findAnswer(int X, int N)
{
    return (N - 1) * 9 + X;
}
 
// Driver Code
public static void Main()
{
    int X = 7, N = 43;
    Console.WriteLine(findAnswer(X, N));
}
}
 
// This code contributed by Ryuga

<?php
// PHP program to find the N-th number
// with digital root as X
 
// Function to find the N-th number
// with digital root as X
function findAnswer($X, $N)
{
    return ($N - 1) * 9 + $X;
}
 
// Driver Code
$X = 7; $N = 43;
echo(findAnswer($X, $N));
 
// This code contributed
// by Code_Mech
?>

<script>
 
// Javascript program to find the N-th number
// with digital root as X
 
// Function to find the N-th number
// with digital root as X
function findAnswer(X, N)
{
    return (N - 1) * 9 + X;
}
 
// Driver Code
let X = 7;
let N = 43;
 
document.write(findAnswer(X, N));
 
// This code is contributed by mohan1240760
 
</script>

385

Complejidad de tiempo: O(1)

Espacio Auxiliar: O(1)