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