Dado un número n y un número d, podemos sumar d a n tantas veces (incluso 0 es posible). La tarea es encontrar la suma de dígitos mínima posible que podemos lograr realizando la operación anterior.
Digit Sum se define como la suma recursiva de los dígitos de un número hasta que es menor que 10.
Ejemplos:
Input: n = 2546, d = 124 Output: 1 2546 + 8*124 = 3538 DigitSum(3538)=1 Input: n = 123, d = 3 Output: 3
Acercarse:
- La primera observación aquí es usar el enfoque %9 para encontrar la suma de dígitos mínima posible de un número n. Si el módulo con 9 es 0, devuelve 9; de lo contrario, devuelve el resto.
- La segunda observación es que a+d*(9k+l) módulo 9 es equivalente a a+d*l módulo 9, por lo tanto, la respuesta a la consulta estará disponible en ninguna adición o en las primeras 8 adiciones de d, después de lo cual la la suma de dígitos se repetirá.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function To find digitsum for a number
int digitsum(int n)
{
// Logic for digitsum
int r = n % 9;
if (r == 0)
return 9;
else
return r;
}
// Function to find minimum digit sum
int find(int n, int d)
{
// Variable to store answer
// Initialise by 10 as the answer
// will always be less than 10
int minimum = 10;
// Values of digitsum will repeat after
// i=8, due to modulo taken with 9
for (int i = 0; i < 9; i++) {
int current = (n + i * d);
minimum = min(minimum, digitsum(current));
}
return minimum;
}
// Driver Code
int main()
{
int n = 2546, d = 124;
cout << "Minimum possible digitsum is :"
<< find(n, d);
return 0;
}
Java
// Java implementation of above approach
import java.io.*;
public class gfg
{
// Function To find digitsum for a number
public int digitsum(int n)
{
// Logic for digitsum
int r = n % 9;
if (r == 0)
return 9;
else
return r;
}
// Function to find minimum digit sum
public int find(int n, int d)
{
// Variable to store answer
// Initialise by 10 as the answer
// will always be less than 10
int minimum = 10;
// Values of digitsum will repeat after
// i=8, due to modulo taken with 9
for (int i = 0; i < 9; i++) {
int current = (n + i * d);
minimum = Math.min(minimum, digitsum(current));
}
return minimum;
}
}
class geek
{
// Driver Code
public static void main(String[]args)
{
gfg g = new gfg();
int n = 2546, d = 124;
System.out.println("Minimum possible digitsum is : "+ (g.find(n, d)));
}
}
//This code is contributed by shs..
Python3
# Python3 implementation of
# above approach
# Function To find digitsum
# for a number
def digitsum(n):
# Logic for digitsum
r = n % 9;
if (r == 0):
return 9;
else:
return r;
# Function to find minimum digit sum
def find(n, d):
# Variable to store answer
# Initialise by 10 as the answer
# will always be less than 10
minimum = 10;
# Values of digitsum will
# repeat after i=8, due to
# modulo taken with 9
for i in range(9):
current = (n + i * d);
minimum = min(minimum,
digitsum(current));
return minimum;
# Driver Code
n = 2546;
d = 124;
print("Minimum possible digitsum is :",
find(n, d));
# This code is contributed by mits
C#
// C# implementation of above approach
using System;
public class gfg
{
// Function To find digitsum for a number
public int digitsum(int n)
{
// Logic for digitsum
int r = n % 9;
if (r == 0)
return 9;
else
return r;
}
// Function to find minimum digit sum
public int find(int n, int d)
{
// Variable to store answer
// Initialise by 10 as the answer
// will always be less than 10
int minimum = 10;
// Values of digitsum will repeat after
// i=8, due to modulo taken with 9
for (int i = 0; i < 9; i++) {
int current = (n + i * d);
minimum = Math.Min(minimum, digitsum(current));
}
return minimum;
}
}
class geek
{
// Driver Code
public static void Main()
{
gfg g = new gfg();
int n = 2546, d = 124;
Console.WriteLine("Minimum possible digitsum is : {0}", (g.find(n, d)));
Console.Read();
}
}
//This code is contributed by SoumikMondal
PHP
<?php
// PHP implementation of
// above approach
// Function To find digitsum
// for a number
function digitsum($n)
{
// Logic for digitsum
$r = $n % 9;
if ($r == 0)
return 9;
else
return $r;
}
// Function to find minimum digit sum
function find($n, $d)
{
// Variable to store answer
// Initialise by 10 as the answer
// will always be less than 10
$minimum = 10;
// Values of digitsum will
// repeat after i=8, due to
// modulo taken with 9
for ($i = 0; $i < 9; $i++)
{
$current = ($n + $i * $d);
$minimum = min($minimum,
digitsum($current));
}
return $minimum;
}
// Driver Code
$n = 2546; $d = 124;
echo "Minimum possible digitsum is :",
find($n, $d);
// This code is contributed
// by Shashank
?>
Javascript
<script>
// javascript implementation of above approach
// Function To find digitsum for a number
function digitsum( n)
{
// Logic for digitsum
var r = n % 9;
if (r == 0)
return 9;
else
return r;
}
// Function to find minimum digit sum
function find( n, d)
{
// Variable to store answer
// Initialise by 10 as the answer
// will always be less than 10
var minimum = 10;
// Values of digitsum will repeat after
// i=8, due to modulo taken with 9
for (var i = 0; i < 9; i++) {
var current = (n + i * d);
minimum = Math.min(minimum, digitsum(current));
}
return minimum;
}
var n = 2546, d = 124;
document.write("Minimum possible digitsum is :" + find(n, d));
</script>
Producción:
Minimum possible digitsum is :1