Dado un número entero n, encuentre la mayor suma de dígitos en todos los divisores de n.
Ejemplos:
Input : n = 12 Output : 6 Explanation: The divisors are: 1 2 3 4 6 12. 6 is maximum sum among all divisors Input : n = 68 Output : 14 Explanation: The divisors are: 1 2 4 68 68 consists of maximum sum of digit
Enfoque ingenuo:
la idea es simple, encontramos todos los divisores de un número uno por uno . Para cada divisor, calculamos la suma de los dígitos . Finalmente, devolvemos la mayor suma de dígitos.
Complejidad de tiempo: O (n log n)
A continuación se muestra la implementación del enfoque anterior:
CPP
// CPP program to find maximum // sum of digits in all divisors // of n numbers. #include <bits/stdc++.h> using namespace std; // Function to get sum of digits int getSum(int n) { int sum = 0; while (n != 0) { sum = sum + n % 10; n = n/10; } return sum; } // returns maximum sum int largestDigitSumdivisior(int n) { int res = 0; for (int i = 1; i <= n; i++) // if i is factor of n // then push the divisor // in the stack. if (n % i == 0) res = max(res, getSum(i)); return res; } // Driver Code int main() { int n = 14; cout << largestDigitSumdivisior(n) << endl; return 0; }
Java
// Java program to find maximum // sum of digits in all divisors // of n numbers. import java.util.*; import java.lang.*; class GfG { // Function to get // sum of digits public static int getSum(int n) { int sum = 0; while (n != 0) { sum = sum + n % 10; n = n/10; } return sum; } // returns maximum sum public static int largestDigitSumdivisior(int n) { int res = 0; for (int i = 1; i <= n; i++) // if i is factor of n // then push the divisor // in the stack. if (n % i == 0) res = Math.max(res, getSum(i)); return res; } // Driver Code public static void main(String argc[]){ int n = 14; System.out.println(largestDigitSumdivisior(n)); } } // This code is contributed // by Sagar Shukla
Python3
# Python3 code to find # maximum sum of digits # in all divisors of n numbers. # Function to get sum of digits def getSum( n ): sum = 0 while n != 0: sum = sum + n % 10 n = int( n / 10 ) return sum # returns maximum sum def largestDigitSumdivisior( n ): res = 0 for i in range(1, n + 1): # if i is factor of n # then push the divisor # in the stack. if n % i == 0: res = max(res, getSum(i)) return res # Driver Code n = 14 print(largestDigitSumdivisior(n) ) # This code is contributed # by "Sharad_Bhardwaj".
C#
// C# program to find maximum // sum of digits in all // divisors of n numbers. using System; class GfG { // Function to get // sum of digits public static int getSum(int n) { int sum = 0; while (n != 0) { sum = sum + n % 10; n = n / 10; } return sum; } // returns maximum sum public static int largestDigitSumdivisior(int n) { int res = 0; for (int i = 1; i <= n; i++) // if i is factor of n // then push the divisor // in the stack. if (n % i == 0) res = Math.Max(res, getSum(i)); return res; } // Driver Code public static void Main() { int n = 14; Console.WriteLine(largestDigitSumdivisior(n)); } } // This code is contributed by vt_m
PHP
<?php // PHP program to find maximum // sum of digits in all // divisors of n numbers. // Function to get // sum of digits function getSum( $n) { $sum = 0; while ($n != 0) { $sum = $sum + $n % 10; $n = $n/10; } return $sum; } // returns maximum sum function largestDigitSumdivisior( $n) { $res = 0; for ($i = 1; $i <= $n; $i++) // if i is factor of n then // push the divisor in // the stack. if ($n % $i == 0) $res = max($res, getSum($i)); return $res; } // Driver Code $n = 14; echo largestDigitSumdivisior($n); // This code is contributed by anuj_67. ?>
Javascript
<script> // Javascript program to find maximum // sum of digits in all divisors // of n numbers. // Function to get sum of digits function getSum(n) { let sum = 0; while (n != 0) { sum = sum + n % 10; n = Math.floor(n/10); } return sum; } // returns maximum sum function largestDigitSumdivisior(n) { let res = 0; for (let i = 1; i <= n; i++) // if i is factor of n // then push the divisor // in the stack. if (n % i == 0) res = Math.max(res, getSum(i)); return res; } // Driver Code let n = 14; document.write(largestDigitSumdivisior(n) + "<br>"); // This code is contributed by Mayank Tyagi </script>
Producción :
7
Un enfoque eficiente será encontrar los divisores en O(sqrt n). Seguimos los mismos pasos que arriba, solo iteramos hasta sqrt(n) y obtenemos i y n/i como sus divisores siempre que n%i==0.
A continuación se muestra la implementación del enfoque anterior:
CPP
// CPP program to find // maximum sum of digits // in all divisors of n // numbers. #include <bits/stdc++.h> using namespace std; // Function to get // sum of digits int getSum(int n) { int sum = 0; while (n != 0) { sum = sum + n % 10; n = n / 10; } return sum; } // returns maximum sum int largestDigitSumdivisior(int n) { int res = 0; // traverse till sqrt(n) for (int i = 1; i <= sqrt(n); i++) // if i is factor of // n then push the // divisor in the stack. if (n % i == 0) { // check for both the divisors res = max(res, getSum(i)); res = max(res,getSum(n / i)); } return res; } // Driver Code int main() { int n = 14; cout << largestDigitSumdivisior(n) << endl; return 0; }
Java
// Java program to find maximum // sum of digits in all divisors // of n numbers. import java.io.*; import java.math.*; class GFG { // Function to get // sum of digits static int getSum(int n) { int sum = 0; while (n != 0) { sum = sum + n % 10; n = n / 10; } return sum; } // returns maximum sum static int largestDigitSumdivisior(int n) { int res = 0; // traverse till sqrt(n) for (int i = 1; i <= Math.sqrt(n); i++) { // if i is factor of // n then push the // divisor in the stack. if (n % i == 0) { // check for both the divisors res = Math.max(res, getSum(i)); res = Math.max(res, getSum(n / i)); } } return res; } // Driver Code public static void main(String args[]) { int n = 14; System.out.println(largestDigitSumdivisior(n)); } } // This code is contributed // by Nikita Tiwari
Python3
# Python 3 program # to find maximum # sum of digits in # all divisors of # n numbers import math # Function to get # sum of digits def getSum(n) : sm = 0 while (n != 0) : sm = sm + n % 10 n = n // 10 return sm # returns maximum sum def largestDigitSumdivisior(n) : res = 0 # traverse till sqrt(n) for i in range(1, (int)(math.sqrt(n))+1) : # if i is factor of n then # push the divisor in the # stack. if (n % i == 0) : # check for both the # divisors res = max(res, getSum(i)) res = max(res, getSum(n // i)) return res # Driver Code n = 14 print(largestDigitSumdivisior(n)) #This code is contributed # by Nikita Tiwari
C#
// C# program to find maximum sum // of digits in all divisors of n // numbers. using System; class GFG { // Function to get // sum of digits static int getSum(int n) { int sum = 0; while (n != 0) { sum = sum + n % 10; n = n / 10; } return sum; } // returns maximum sum static int largestDigitSumdivisior(int n) { int res = 0; // traverse till sqrt(n) for (int i = 1; i <= Math.Sqrt(n); i++) { // if i is factor of n then push the // divisor in the stack. if (n % i == 0) { // check for both the divisors res = Math.Max(res, getSum(i)); res = Math.Max(res, getSum(n / i)); } } return res; } // Driver Code public static void Main() { int n = 14; Console.WriteLine(largestDigitSumdivisior(n)); } } // This code is contributed by Vt_m
PHP
<?php // PHP program to find maximum // sum of digits in all // divisors of n numbers // Function to get // sum of digits function getSum($n) { $sum = 0; while ($n != 0) { $sum = $sum + $n % 10; $n = $n / 10; } return $sum; } // returns maximum sum function largestDigitSumdivisior( $n) { $res = 0; // traverse till sqrt(n) for ($i = 1; $i <= sqrt($n); $i++) // if i is factor of // n then push the // divisor in the stack. if ($n % $i == 0) { // check for both the divisors $res = max($res, getSum($i)); $res = max($res, getSum($n / $i)); } return $res; } // Driver Code $n = 14; echo largestDigitSumdivisior($n); // This code is contributed by anuj_67. ?>
Javascript
<script> // JavaScript program to find // maximum sum of digits // in all divisors of n // numbers. // Function to get // sum of digits function getSum(n) { var sum = 0; while (n != 0) { sum = sum + n % 10; n = parseInt(n / 10); } return sum; } // returns maximum sum function largestDigitSumdivisior(n) { var res = 0; // traverse till sqrt(n) for (var i = 1; i <= Math.sqrt(n); i++) // if i is factor of // n then push the // divisor in the stack. if (n % i == 0) { // check for both the divisors res = Math.max(res, getSum(i)); res = Math.max(res,getSum(n / i)); } return res; } // Driver Code var n = 14; document.write(largestDigitSumdivisior(n)); </script>
Producción :
7
Complejidad de tiempo: O(sqrt(n) log n)
Publicación traducida automáticamente
Artículo escrito por shrikanth13 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA