Raíz digital (suma digital repetida) del entero grande dado

La raíz digital de un entero positivo se encuentra sumando los dígitos del entero. Si el valor resultante es un solo dígito, entonces ese dígito es la raíz digital. Si el valor resultante contiene dos o más dígitos, esos dígitos se suman y se repite el proceso. Esto continúa todo el tiempo que sea necesario para obtener un solo dígito.
Dado un número, la tarea es encontrar su raíz digital. El número de entrada puede ser grande y puede que no sea posible almacenarlo incluso si usamos long long int.
Preguntado en ACM-ICPC
Ejemplos:

Entrada: num = “1234”
Salida: 1
Explicación: La suma de 1+2+3+4 = 10, digSum(x) == 10, por lo tanto, ans será 1+0 = 1
Entrada: num = “5674”
Salida : 4 

Hemos discutido una solución para números que pueden caber mucho tiempo en la publicación a continuación. 
Encontrar la suma de los dígitos de un número hasta que la suma se convierte en un solo dígito
En esta publicación, se analizan enfoques similares para números grandes.

Método 1
Encuentre la raíz digital de 65785412 
Pasos:  

1. Averiguar todos los dígitos de un número
2. Suma todos los números uno por uno
3. Si la suma final es de dos dígitos, agregue nuevamente para que sea de un solo dígito
4. El resultado obtenido en un solo dígito es la raíz digital de un número

Ejemplo: 
Entrada: 65785412 
Buscar raíz digital: (6 + 5 + 7 + 8 + 5 + 4 + 1 + 2) = 38 => 11 => (1 + 1) = 2 
Salida: 2 
 

Método 2
La idea se basa en el hecho de que para un número distinto de cero num, la raíz digital es 9 si el número es divisible por 9, de lo contrario, la raíz digital es num % 9. (Consulte http://www.sjsu.edu/ facultad/watkins/Digitsum0.htm para más detalles)
Encuentre la raíz digital de 65785412 
Pasos: 

1. Suma de dígitos = 6 + 5 + 7 + 8 + 5 + 4 + 1 + 2 = 38
2. Como 38 no es múltiplo de 9, la raíz digital es 38 % 9 = 2.

// C++ program to find  digital root of a number
#include<bits/stdc++.h>
using namespace std;
 
// Returns digital root of num
int digitalRoot(string num)
{
    // If num is 0.
    if (num.compare("0") == 0)
        return 0;
 
    // Count sum of digits under mod 9
    int ans = 0;
    for (int i=0; i<num.length(); i++)
        ans = (ans + num[i]-'0') % 9;
 
    // If digit sum is multiple of 9, answer
    // 9, else remainder with 9.
    return (ans == 0)? 9 : ans % 9;
}
 
// Driver code
int main()
{
    string num = "65785412";
 
    // Calling digitalRoot function
    cout<< digitalRoot(num) <<endl;
 
    return 0;
}
 
// Note: Special case when num = "00..."
// program will not give correct output.

// Java code for digital root
import java.util.*;
  
public class GfG {
      
    static int digroot(int n)
    {
        int root = 0;
  
        // Loop to do sum while
        // sum is not less than
        // or equal to 9
        while (n > 0 || root > 9)
        {
             if (n == 0) {
                n = root;
                root = 0;
            }
             
            root += n % 10;
            n /= 10;
        }
        return root;
    }
      
    // Driver code
    public static void main(String argc[])
    {
        int n = 65785412;
        System.out.println(digroot(n));
    }
}
 
// This code is contributed by Gitanjali.
// This code will run for 0000 testcase also.

# Python3 program to find digital root
# of a number
import math
 
# Returns digital root of num
def digitalRoot(num):
     
    # If num is 0.
    if (num == "0"):
        return 0
 
    # Count sum of digits under mod 9
    ans = 0
    for i in range (0, len(num)):
        ans = (ans + int(num[i])) % 9
         
 
    # If digit sum is multiple of 9, answer
    # 9, else remainder with 9.
    if(ans == 0):
        return 9
    else:
        return ans % 9
 
# Driver method
num = "65785412"
 
# Calling digitalRoot function
print (digitalRoot(num))
 
# This code is contributed by Gitanjali.

// C# code for digital root
using System;
 
class GfG {
     
    static int digroot(int n)
    {
        int root = 0;
 
        // Loop to do sum while
        // sum is not less than
        // or equal to 9
        while (n > 0 || root > 9)
        {
            if (n == 0) {
                n = root;
                root = 0;
            }
             
            root += n % 10;
            n /= 10;
        }
        return root;
    }
     
    // Driver code
    public static void Main()
    {
        int n = 65785412;
        Console.Write(digroot(n));
    }
}
 
// This code is contributed by Smitha
// This code will run for 0000 testcase also.

<?php
// PHP program to find
// digital root of a number
 
// Returns digital root of num
function digroot($n)
{
    $root = 0;
 
    // Loop to do sum while
    // sum is not less than
    // or equal to 9
    while ($n > 0 || $root > 9)
    {
        if ($n == 0)
        {
            $n = $root;
            $root = 0;
        }
         
        $root += $n % 10;
        $n /= 10;
    }
    return $root;
}
 
// Driver code
$num = 65785412;
 
// Calling digitalRoot function
echo digroot($num);
 
// This code is contributed by Sam007
?>

<script>
    // Javascript code for digital root
     
    function digroot(n)
    {
        let root = 0;
   
        // Loop to do sum while
        // sum is not less than
        // or equal to 9
        while (n > 0 || root > 9)
        {
            if (n == 0) {
                n = root;
                root = 0;
            }
               
            root += n % 10;
            n = parseInt(n / 10, 10);
        }
        return root;
    }
     
    let n = 65785412;
      document.write(digroot(n));
     
</script>

2

Complejidad de tiempo: O(n), donde n es el tamaño de la string dada num
Espacio auxiliar: O(1)

Este artículo es una contribución de Shiv Pratap Singh . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.