Colocación de Sudo[1.7] | Mayor raíz digital

Dado un número N, debe encontrar un divisor de N tal que la Raíz digital de ese divisor sea la mayor entre todos los demás divisores de N. Si más de un divisor da la misma Raíz digital mayor, genere el divisor máximo.
La raíz digital de un número no negativo se puede obtener sumando repetidamente los dígitos del número hasta llegar a un solo dígito. Ejemplo: DigitalRoot(98)=9+8=>17=>1+7=>8(¡un solo dígito!). La tarea es imprimir el mayor divisor que tenga la mayor raíz digital seguido de un espacio y la raíz digital de ese divisor.
Ejemplos: 
 

Entrada: N = 10 
Salida: 5 5 
Los divisores de 10 son: 1, 2, 5, 10. Las raíces digitales de estos divisores son las siguientes: 
1=>1, 2=>2, 5=>5, 10= >1. La Raíz Digital más grande es 5 que es producida por el divisor 5, entonces la respuesta es 5 5
Entrada: N = 18 
Salida: 18 9 
Los divisores de 18 son: 1, 2, 3, 6, 9, 18. Las Raíces Digitales de estos los divisores son los siguientes: 
1=>1, 2=>2, 3=>3, 6=>6, 9=>9, 18=>9. Como podemos ver, tanto 9 como 18 tienen la raíz digital más grande de 9. Entonces seleccionamos el máximo de esos divisores, que es Max(9, 18)=18. Entonces la respuesta es 18 9

Un enfoque ingenuo será iterar hasta N y encontrar todos los factores y sus sumas de dígitos . Guarde los más grandes entre ellos e imprímalos.
Complejidad de tiempo: O(N) 
Un enfoque eficiente es hacer un bucle hasta sqrt(N) , entonces los factores serán i y n/i. Verifique la suma de dígitos más grande entre ellos, en caso de sumas de dígitos similares, almacene el factor más grande. Una vez completada la iteración, imprímelas. 
A continuación se muestra la implementación del enfoque anterior. 
 

C++

// C++ program to print the
// digital roots of a number
#include <bits/stdc++.h>
using namespace std;
 
// Function to return
// dig-sum
int summ(int n)
{
    if (n == 0)
        return 0;
    return (n % 9 == 0) ? 9 : (n % 9);
}
 
// Function to print the Digital Roots
void printDigitalRoot(int n)
{
 
    // store the largest digital roots
    int maxi = 1;
    int dig = 1;
 
    // Iterate till sqrt(n)
    for (int i = 1; i <= sqrt(n); i++) {
 
        // if i is a factor
        if (n % i == 0) {
            // get the digit sum of both
            // factors i and n/i
            int d1 = summ(n / i);
            int d2 = summ(i);
 
            // if digit sum is greater
            // then previous maximum
            if (d1 > maxi) {
                dig = n / i;
                maxi = d1;
            }
 
            // if digit sum is greater
            // then previous maximum
            if (d2 > maxi) {
                dig = i;
                maxi = d2;
            }
 
            // if digit sum is same as
            // then previous maximum, then
            // check for larger divisor
            if (d1 == maxi) {
                if (dig < (n / i)) {
                    dig = n / i;
                    maxi = d1;
                }
            }
 
            // if digit sum is same as
            // then previous maximum, then
            // check for larger divisor
            if (d2 == maxi) {
                if (dig < i) {
                    dig = i;
                    maxi = d2;
                }
            }
        }
    }
 
    // Print the digital roots
    cout << dig << " " << maxi << endl;
}
 
// Driver Code
int main()
{
    int n = 10;
 
    // Function call to print digital roots
    printDigitalRoot(n);
    return 0;
}

Java

// Java program to print the digital
// roots of a number
class GFG
{
     
// Function to return dig-sum
static int summ(int n)
{
    if (n == 0)
        return 0;
    return (n % 9 == 0) ? 9 : (n % 9);
}
 
// Function to print the Digital Roots
static void printDigitalRoot(int n)
{
 
    // store the largest digital roots
    int maxi = 1;
    int dig = 1;
 
    // Iterate till sqrt(n)
    for (int i = 1; i <= Math.sqrt(n); i++)
    {
 
        // if i is a factor
        if (n % i == 0)
        {
            // get the digit sum of both
            // factors i and n/i
            int d1 = summ(n / i);
            int d2 = summ(i);
 
            // if digit sum is greater
            // then previous maximum
            if (d1 > maxi)
            {
                dig = n / i;
                maxi = d1;
            }
 
            // if digit sum is greater
            // then previous maximum
            if (d2 > maxi)
            {
                dig = i;
                maxi = d2;
            }
 
            // if digit sum is same as
            // then previous maximum, then
            // check for larger divisor
            if (d1 == maxi)
            {
                if (dig < (n / i))
                {
                    dig = n / i;
                    maxi = d1;
                }
            }
 
            // if digit sum is same as
            // then previous maximum, then
            // check for larger divisor
            if (d2 == maxi)
            {
                if (dig < i)
                {
                    dig = i;
                    maxi = d2;
                }
            }
        }
    }
 
    // Print the digital roots
    System.out.println(dig + " " + maxi);
}
 
// Driver Code
public static void main(String[] args)
{
    int n = 10;
 
    // Function call to print digital roots
    printDigitalRoot(n);
}
}
// This code is contributed by mits

Python3

# Python3 program to print the digital
# roots of a number
 
# Function to return dig-sum
def summ(n):
    if (n == 0):
        return 0;
    if(n % 9 == 0):
        return 9;
    else:
        return (n % 9);
 
# Function to print the Digital Roots
def printDigitalRoot(n):
 
    # store the largest digital roots
    maxi = 1;
    dig = 1;
 
    # Iterate till sqrt(n)
    for i in range(1, int(pow(n, 1/2) + 1)):
 
        # if i is a factor
        if (n % i == 0):
             
            # get the digit sum of both
            # factors i and n/i
            d1 = summ(n / i);
            d2 = summ(i);
 
            # if digit sum is greater
            # then previous maximum
            if (d1 > maxi):
                dig = n / i;
                maxi = d1;
             
            # if digit sum is greater
            # then previous maximum
            if (d2 > maxi):
                dig = i;
                maxi = d2;
             
            # if digit sum is same as
            # then previous maximum, then
            # check for larger divisor
            if (d1 == maxi):
                if (dig < (n / i)):
                    dig = n / i;
                    maxi = d1;
 
            # if digit sum is same as
            # then previous maximum, then
            # check for larger divisor
            if (d2 == maxi):
                if (dig < i):
                    dig = i;
                    maxi = d2;
                 
    # Print the digital roots
    print(int(dig), " ", int(maxi));
 
# Driver Code
if __name__ == '__main__':
    n = 10;
 
    # Function call to prdigital roots
    printDigitalRoot(n);
     
# This code is contributed by 29AjayKumar

C#

// C# program to print the digital
// roots of a number
using System;
 
class GFG
{
     
// Function to return dig-sum
static int summ(int n)
{
    if (n == 0)
        return 0;
    return (n % 9 == 0) ? 9 : (n % 9);
}
 
// Function to print the Digital Roots
static void printDigitalRoot(int n)
{
 
    // store the largest digital roots
    int maxi = 1;
    int dig = 1;
 
    // Iterate till sqrt(n)
    for (int i = 1; i <= Math.Sqrt(n); i++)
    {
 
        // if i is a factor
        if (n % i == 0)
        {
            // get the digit sum of both
            // factors i and n/i
            int d1 = summ(n / i);
            int d2 = summ(i);
 
            // if digit sum is greater
            // then previous maximum
            if (d1 > maxi)
            {
                dig = n / i;
                maxi = d1;
            }
 
            // if digit sum is greater
            // then previous maximum
            if (d2 > maxi)
            {
                dig = i;
                maxi = d2;
            }
 
            // if digit sum is same as
            // then previous maximum, then
            // check for larger divisor
            if (d1 == maxi)
            {
                if (dig < (n / i))
                {
                    dig = n / i;
                    maxi = d1;
                }
            }
 
            // if digit sum is same as
            // then previous maximum, then
            // check for larger divisor
            if (d2 == maxi)
            {
                if (dig < i)
                {
                    dig = i;
                    maxi = d2;
                }
            }
        }
    }
 
    // Print the digital roots
    Console.WriteLine(dig + " " + maxi);
}
 
// Driver Code
public static void Main()
{
    int n = 10;
 
    // Function call to print digital roots
    printDigitalRoot(n);
}
}
 
// This code is contributed
// by Akanksha Rai

Javascript

<script>
// javascript program to print the digital
// roots of a number    // Function to return dig-sum
    function summ(n) {
        if (n == 0)
            return 0;
        return (n % 9 == 0) ? 9 : (n % 9);
    }
 
    // Function to print the Digital Roots
    function printDigitalRoot(n) {
 
        // store the largest digital roots
        var maxi = 1;
        var dig = 1;
 
        // Iterate till sqrt(n)
        for (i = 1; i <= Math.sqrt(n); i++) {
 
            // if i is a factor
            if (n % i == 0) {
                // get the digit sum of both
                // factors i and n/i
                var d1 = summ(n / i);
                var d2 = summ(i);
 
                // if digit sum is greater
                // then previous maximum
                if (d1 > maxi) {
                    dig = n / i;
                    maxi = d1;
                }
 
                // if digit sum is greater
                // then previous maximum
                if (d2 > maxi) {
                    dig = i;
                    maxi = d2;
                }
 
                // if digit sum is same as
                // then previous maximum, then
                // check for larger divisor
                if (d1 == maxi) {
                    if (dig < (n / i)) {
                        dig = n / i;
                        maxi = d1;
                    }
                }
 
                // if digit sum is same as
                // then previous maximum, then
                // check for larger divisor
                if (d2 == maxi) {
                    if (dig < i) {
                        dig = i;
                        maxi = d2;
                    }
                }
            }
        }
 
        // Print the digital roots
        document.write(dig + " " + maxi);
    }
 
    // Driver Code
     
        var n = 10;
 
        // Function call to print digital roots
        printDigitalRoot(n);
 
// This code is contributed by todaysgaurav
</script>
Producción: 

5 5

 

Complejidad del tiempo: O(sqrt(N))
 

Publicación traducida automáticamente

Artículo escrito por Striver y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *