Dado un número n, encuentre la suma de los dígitos en todos los números del 1 al n.
Ejemplos:
Input: n = 5 Output: Sum of digits in numbers from 1 to 5 = 15 Input: n = 12 Output: Sum of digits in numbers from 1 to 12 = 51 Input: n = 328 Output: Sum of digits in numbers from 1 to 328 = 3241
Solución ingenua: una solución ingenua es recorrer todos los números x del 1 al n y calcular la suma en x recorriendo todos los dígitos de x. A continuación se muestra la implementación de esta idea.
Implementación:
C++
// A Simple C++ program to compute sum of digits in numbers from 1 to n
#include<bits/stdc++.h>
using namespace std;
int sumOfDigits(int );
// Returns sum of all digits in numbers from 1 to n
int sumOfDigitsFrom1ToN(int n)
{
int result = 0; // initialize result
// One by one compute sum of digits in every number from
// 1 to n
for (int x = 1; x <= n; x++)
result += sumOfDigits(x);
return result;
}
// A utility function to compute sum of digits in a
// given number x
int sumOfDigits(int x)
{
int sum = 0;
while (x != 0)
{
sum += x %10;
x = x /10;
}
return sum;
}
// Driver Program
int main()
{
int n = 328;
cout << "Sum of digits in numbers from 1 to " << n << " is "
<< sumOfDigitsFrom1ToN(n);
return 0;
}
Java
// A Simple JAVA program to compute sum of
// digits in numbers from 1 to n
import java.io.*;
class GFG {
// Returns sum of all digits in numbers
// from 1 to n
static int sumOfDigitsFrom1ToN(int n)
{
int result = 0; // initialize result
// One by one compute sum of digits
// in every number from 1 to n
for (int x = 1; x <= n; x++)
result += sumOfDigits(x);
return result;
}
// A utility function to compute sum
// of digits in a given number x
static int sumOfDigits(int x)
{
int sum = 0;
while (x != 0)
{
sum += x % 10;
x = x / 10;
}
return sum;
}
// Driver Program
public static void main(String args[])
{
int n = 328;
System.out.println("Sum of digits in numbers"
+" from 1 to " + n + " is "
+ sumOfDigitsFrom1ToN(n));
}
}
/*This code is contributed by Nikita Tiwari.*/
Python3
# A Simple Python program to compute sum
# of digits in numbers from 1 to n
# Returns sum of all digits in numbers
# from 1 to n
def sumOfDigitsFrom1ToN(n) :
result = 0 # initialize result
# One by one compute sum of digits
# in every number from 1 to n
for x in range(1, n+1) :
result = result + sumOfDigits(x)
return result
# A utility function to compute sum of
# digits in a given number x
def sumOfDigits(x) :
sum = 0
while (x != 0) :
sum = sum + x % 10
x = x // 10
return sum
# Driver Program
n = 328
print("Sum of digits in numbers from 1 to", n, "is", sumOfDigitsFrom1ToN(n))
# This code is contributed by Nikita Tiwari.
C#
// A Simple C# program to compute sum of
// digits in numbers from 1 to n
using System;
public class GFG {
// Returns sum of all digits in numbers
// from 1 to n
static int sumOfDigitsFrom1ToN(int n)
{
// initialize result
int result = 0;
// One by one compute sum of digits
// in every number from 1 to n
for (int x = 1; x <= n; x++)
result += sumOfDigits(x);
return result;
}
// A utility function to compute sum
// of digits in a given number x
static int sumOfDigits(int x)
{
int sum = 0;
while (x != 0)
{
sum += x % 10;
x = x / 10;
}
return sum;
}
// Driver Program
public static void Main()
{
int n = 328;
Console.WriteLine("Sum of digits"
+ " in numbers from 1 to "
+ n + " is "
+ sumOfDigitsFrom1ToN(n));
}
}
// This code is contributed by shiv_bhakt.
PHP
<?php
// A Simple php program to compute sum
//of digits in numbers from 1 to n
// Returns sum of all digits in
// numbers from 1 to n
function sumOfDigitsFrom1ToN($n)
{
$result = 0; // initialize result
// One by one compute sum of digits
// in every number from 1 to n
for ($x = 1; $x <= $n; $x++)
$result += sumOfDigits($x);
return $result;
}
// A utility function to compute sum
// of digits in a given number x
function sumOfDigits($x)
{
$sum = 0;
while ($x != 0)
{
$sum += $x %10;
$x = $x /10;
}
return $sum;
}
// Driver Program
$n = 328;
echo "Sum of digits in numbers from"
. " 1 to " . $n . " is "
. sumOfDigitsFrom1ToN($n);
// This code is contributed by ajit
?>
Javascript
<script>
// A Simple Javascript program to compute sum of
// digits in numbers from 1 to n
// Returns sum of all digits in numbers
// from 1 to n
function sumOfDigitsFrom1ToN(n)
{
// initialize result
let result = 0;
// One by one compute sum of digits
// in every number from 1 to n
for (let x = 1; x <= n; x++)
result += sumOfDigits(x);
return result;
}
// A utility function to compute sum
// of digits in a given number x
function sumOfDigits(x)
{
let sum = 0;
while (x != 0)
{
sum += x % 10;
x = parseInt(x / 10, 10);
}
return sum;
}
let n = 328;
document.write("Sum of digits"
+ " in numbers from 1 to "
+ n + " is "
+ sumOfDigitsFrom1ToN(n));
// This code is contributed by divyeshrabadiya07.
</script>
C
// A Simple C program to compute sum of digits in numbers from 1 to n
#include<stdio.h>
//Function declaration
int sumOfDigits(int x);
int sumOfDigitsFrom1ToN(int n);
// Returns sum of all digits in numbers from 1 to n
int sumOfDigitsFrom1ToN(int n)
{
int result = 0; // initialize result
// One by one compute sum of digits in every number from
// 1 to n
for (int x = 1; x <= n; x++)
result += sumOfDigits(x);
return result;
}
// A utility function to compute sum of digits in a
// given number x
int sumOfDigits(int x)
{
int sum = 0;
while (x != 0)
{
sum += x %10;
x = x /10;
}
return sum;
}
// Driver Program
int main()
{
int n = 328;
printf("Sum of digits in numbers from 1 to %d is : %d",n,sumOfDigitsFrom1ToN(n));
return 0;
}
Producción
Sum of digits in numbers from 1 to 328 is 3241
Complejidad de tiempo: O(N*len(N)), donde len(X) da el no. de dígitos en X.
Espacio Auxiliar: O(1)
Solución eficiente:
Arriba hay una solución ingenua. Podemos hacerlo de manera más eficiente encontrando un patrón.
Tomemos algunos ejemplos.
sum(9) = 1 + 2 + 3 + 4 ........... + 9
= 9*10/2
= 45
sum(99) = 45 + (10 + 45) + (20 + 45) + ..... (90 + 45)
= 45*10 + (10 + 20 + 30 ... 90)
= 45*10 + 10(1 + 2 + ... 9)
= 45*10 + 45*10
= sum(9)*10 + 45*10
sum(999) = sum(99)*10 + 45*100
En general, podemos calcular sum(10 d – 1) usando la siguiente fórmula
sum(10d - 1) = sum(10d-1 - 1) * 10 + 45*(10d-1)
En la implementación a continuación, la fórmula anterior se implementa utilizando programación dinámica ya que hay subproblemas superpuestos.
La fórmula anterior es un paso central de la idea. A continuación se muestra el algoritmo completo.
Algoritmo: suma(n)
1) Find number of digits minus one in n. Let this value be 'd'.
For 328, d is 2.
2) Compute some of digits in numbers from 1 to 10d - 1.
Let this sum be w. For 328, we compute sum of digits from 1 to
99 using above formula.
3) Find Most significant digit (msd) in n. For 328, msd is 3.
4) Overall sum is sum of following terms
a) Sum of digits in 1 to "msd * 10d - 1". For 328, sum of
digits in numbers from 1 to 299.
For 328, we compute 3*sum(99) + (1 + 2)*100. Note that sum of
sum(299) is sum(99) + sum of digits from 100 to 199 + sum of digits
from 200 to 299.
Sum of 100 to 199 is sum(99) + 1*100 and sum of 299 is sum(99) + 2*100.
In general, this sum can be computed as w*msd + (msd*(msd-1)/2)*10d
b) Sum of digits in msd * 10d to n. For 328, sum of digits in
300 to 328.
For 328, this sum is computed as 3*29 + recursive call "sum(28)"
In general, this sum can be computed as msd * (n % (msd*10d) + 1)
+ sum(n % (10d))
A continuación se muestra la implementación del algoritmo anterior.
C++
// C++ program to compute sum of digits in numbers from 1 to n
#include<bits/stdc++.h>
using namespace std;
// Function to computer sum of digits in numbers from 1 to n
// Comments use example of 328 to explain the code
int sumOfDigitsFrom1ToN(int n)
{
// base case: if n<10 return sum of
// first n natural numbers
if (n<10)
return n*(n+1)/2;
// d = number of digits minus one in n. For 328, d is 2
int d = log10(n);
// computing sum of digits from 1 to 10^d-1,
// d=1 a[0]=0;
// d=2 a[1]=sum of digit from 1 to 9 = 45
// d=3 a[2]=sum of digit from 1 to 99 = a[1]*10 + 45*10^1 = 900
// d=4 a[3]=sum of digit from 1 to 999 = a[2]*10 + 45*10^2 = 13500
int *a = new int[d+1];
a[0] = 0, a[1] = 45;
for (int i=2; i<=d; i++)
a[i] = a[i-1]*10 + 45*ceil(pow(10,i-1));
// computing 10^d
int p = ceil(pow(10, d));
// Most significant digit (msd) of n,
// For 328, msd is 3 which can be obtained using 328/100
int msd = n/p;
// EXPLANATION FOR FIRST and SECOND TERMS IN BELOW LINE OF CODE
// First two terms compute sum of digits from 1 to 299
// (sum of digits in range 1-99 stored in a[d]) +
// (sum of digits in range 100-199, can be calculated as 1*100 + a[d]
// (sum of digits in range 200-299, can be calculated as 2*100 + a[d]
// The above sum can be written as 3*a[d] + (1+2)*100
// EXPLANATION FOR THIRD AND FOURTH TERMS IN BELOW LINE OF CODE
// The last two terms compute sum of digits in number from 300 to 328
// The third term adds 3*29 to sum as digit 3 occurs in all numbers
// from 300 to 328
// The fourth term recursively calls for 28
return msd*a[d] + (msd*(msd-1)/2)*p +
msd*(1+n%p) + sumOfDigitsFrom1ToN(n%p);
}
// Driver Program
int main()
{
int n = 328;
cout << "Sum of digits in numbers from 1 to " << n << " is "
<< sumOfDigitsFrom1ToN(n);
return 0;
}
Java
// JAVA program to compute sum of digits
// in numbers from 1 to n
import java.io.*;
import java.math.*;
class GFG{
// Function to computer sum of digits in
// numbers from 1 to n. Comments use
// example of 328 to explain the code
static int sumOfDigitsFrom1ToN(int n)
{
// base case: if n<10 return sum of
// first n natural numbers
if (n < 10)
return (n * (n + 1) / 2);
// d = number of digits minus one in
// n. For 328, d is 2
int d = (int)(Math.log10(n));
// computing sum of digits from 1 to 10^d-1,
// d=1 a[0]=0;
// d=2 a[1]=sum of digit from 1 to 9 = 45
// d=3 a[2]=sum of digit from 1 to 99 =
// a[1]*10 + 45*10^1 = 900
// d=4 a[3]=sum of digit from 1 to 999 =
// a[2]*10 + 45*10^2 = 13500
int a[] = new int[d+1];
a[0] = 0; a[1] = 45;
for (int i = 2; i <= d; i++)
a[i] = a[i-1] * 10 + 45 *
(int)(Math.ceil(Math.pow(10, i-1)));
// computing 10^d
int p = (int)(Math.ceil(Math.pow(10, d)));
// Most significant digit (msd) of n,
// For 328, msd is 3 which can be obtained
// using 328/100
int msd = n / p;
// EXPLANATION FOR FIRST and SECOND TERMS IN
// BELOW LINE OF CODE
// First two terms compute sum of digits from
// 1 to 299
// (sum of digits in range 1-99 stored in a[d]) +
// (sum of digits in range 100-199, can be
// calculated as 1*100 + a[d]
// (sum of digits in range 200-299, can be
// calculated as 2*100 + a[d]
// The above sum can be written as 3*a[d] +
// (1+2)*100
// EXPLANATION FOR THIRD AND FOURTH TERMS IN
// BELOW LINE OF CODE
// The last two terms compute sum of digits in
// number from 300 to 328. The third term adds
// 3*29 to sum as digit 3 occurs in all numbers
// from 300 to 328. The fourth term recursively
// calls for 28
return (msd * a[d] + (msd * (msd - 1) / 2) * p +
msd * (1 + n % p) + sumOfDigitsFrom1ToN(n % p));
}
// Driver Program
public static void main(String args[])
{
int n = 328;
System.out.println("Sum of digits in numbers " +
"from 1 to " +n + " is " +
sumOfDigitsFrom1ToN(n));
}
}
/*This code is contributed by Nikita Tiwari.*/
Python3
# PYTHON 3 program to compute sum of digits
# in numbers from 1 to n
import math
# Function to computer sum of digits in
# numbers from 1 to n. Comments use example
# of 328 to explain the code
def sumOfDigitsFrom1ToN( n) :
# base case: if n<10 return sum of
# first n natural numbers
if (n<10) :
return (n*(n+1)/2)
# d = number of digits minus one in n.
# For 328, d is 2
d = (int)(math.log10(n))
"""computing sum of digits from 1 to 10^d-1,
d=1 a[0]=0;
d=2 a[1]=sum of digit from 1 to 9 = 45
d=3 a[2]=sum of digit from 1 to 99 = a[1]*10
+ 45*10^1 = 900
d=4 a[3]=sum of digit from 1 to 999 = a[2]*10
+ 45*10^2 = 13500"""
a = [0] * (d + 1)
a[0] = 0
a[1] = 45
for i in range(2, d+1) :
a[i] = a[i-1] * 10 + 45 * (int)(math.ceil(math.pow(10,i-1)))
# computing 10^d
p = (int)(math.ceil(math.pow(10, d)))
# Most significant digit (msd) of n,
# For 328, msd is 3 which can be obtained
# using 328/100
msd = n//p
"""EXPLANATION FOR FIRST and SECOND TERMS IN
BELOW LINE OF CODE
First two terms compute sum of digits from 1 to 299
(sum of digits in range 1-99 stored in a[d]) +
(sum of digits in range 100-199, can be calculated
as 1*100 + a[d]. (sum of digits in range 200-299,
can be calculated as 2*100 + a[d]
The above sum can be written as 3*a[d] + (1+2)*100
EXPLANATION FOR THIRD AND FOURTH TERMS IN BELOW
LINE OF CODE
The last two terms compute sum of digits in number
from 300 to 328. The third term adds 3*29 to sum
as digit 3 occurs in all numbers from 300 to 328.
The fourth term recursively calls for 28"""
return (int)(msd * a[d] + (msd*(msd-1) // 2) * p +
msd * (1 + n % p) + sumOfDigitsFrom1ToN(n % p))
# Driver Program
n = 328
print("Sum of digits in numbers from 1 to",
n ,"is",sumOfDigitsFrom1ToN(n))
# This code is contributed by Nikita Tiwari.
C#
// C# program to compute sum of digits
// in numbers from 1 to n
using System;
public class GFG {
// Function to computer sum of digits in
// numbers from 1 to n. Comments use
// example of 328 to explain the code
static int sumOfDigitsFrom1ToN(int n)
{
// base case: if n<10 return sum of
// first n natural numbers
if (n < 10)
return (n * (n + 1) / 2);
// d = number of digits minus one in
// n. For 328, d is 2
int d = (int)(Math.Log(n) / Math.Log(10));
// computing sum of digits from 1 to 10^d-1,
// d=1 a[0]=0;
// d=2 a[1]=sum of digit from 1 to 9 = 45
// d=3 a[2]=sum of digit from 1 to 99 =
// a[1]*10 + 45*10^1 = 900
// d=4 a[3]=sum of digit from 1 to 999 =
// a[2]*10 + 45*10^2 = 13500
int[] a = new int[d+1];
a[0] = 0; a[1] = 45;
for (int i = 2; i <= d; i++)
a[i] = a[i-1] * 10 + 45 *
(int)(Math.Ceiling(Math.Pow(10, i-1)));
// computing 10^d
int p = (int)(Math.Ceiling(Math.Pow(10, d)));
// Most significant digit (msd) of n,
// For 328, msd is 3 which can be obtained
// using 328/100
int msd = n / p;
// EXPLANATION FOR FIRST and SECOND TERMS IN
// BELOW LINE OF CODE
// First two terms compute sum of digits from
// 1 to 299
// (sum of digits in range 1-99 stored in a[d]) +
// (sum of digits in range 100-199, can be
// calculated as 1*100 + a[d]
// (sum of digits in range 200-299, can be
// calculated as 2*100 + a[d]
// The above sum can be written as 3*a[d] +
// (1+2)*100
// EXPLANATION FOR THIRD AND FOURTH TERMS IN
// BELOW LINE OF CODE
// The last two terms compute sum of digits in
// number from 300 to 328. The third term adds
// 3*29 to sum as digit 3 occurs in all numbers
// from 300 to 328. The fourth term recursively
// calls for 28
return (msd * a[d] + (msd * (msd - 1) / 2) * p +
msd * (1 + n % p) + sumOfDigitsFrom1ToN(n % p));
}
// Driver Program
public static void Main()
{
int n = 328;
Console.WriteLine("Sum of digits in numbers " +
"from 1 to " +n + " is " +
sumOfDigitsFrom1ToN(n));
}
}
// This code is contributed by shiv_bhakt.
PHP
<?php
// PHP program to compute sum of digits
// in numbers from 1 to n
// Function to computer sum of digits in
// numbers from 1 to n. Comments use
// example of 328 to explain the code
function sumOfDigitsFrom1ToN($n)
{
// base case: if n<10 return sum of
// first n natural numbers
if ($n < 10)
return ($n * ($n + 1) / 2);
// d = number of digits minus one in
// n. For 328, d is 2
$d = (int)(log10($n));
// computing sum of digits from 1
// to 10^d-1, d=1 a[0]=0;
// d=2 a[1]=sum of digit from 1 to 9 = 45
// d=3 a[2]=sum of digit from 1 to 99 =
// a[1]*10 + 45*10^1 = 900
// d=4 a[3]=sum of digit from 1 to 999 =
// a[2]*10 + 45*10^2 = 13500
$a[$d + 1] = array();
$a[0] = 0;
$a[1] = 45;
for ($i = 2; $i <= $d; $i++)
$a[$i] = $a[$i - 1] * 10 + 45 *
(int)(ceil(pow(10, $i - 1)));
// computing 10^d
$p = (int)(ceil(pow(10, $d)));
// Most significant digit (msd) of n,
// For 328, msd is 3 which can be obtained
// using 328/100
$msd = (int)($n / $p);
// EXPLANATION FOR FIRST and SECOND
// TERMS IN BELOW LINE OF CODE
// First two terms compute sum of
// digits from 1 to 299
// (sum of digits in range 1-99 stored
// in a[d]) + (sum of digits in range
// 100-199, can be calculated as 1*100 + a[d]
// (sum of digits in range 200-299,
// can be calculated as 2*100 + a[d]
// The above sum can be written as
// 3*a[d] + (1+2)*100
// EXPLANATION FOR THIRD AND FOURTH
// TERMS IN BELOW LINE OF CODE
// The last two terms compute sum of digits in
// number from 300 to 328. The third term adds
// 3*29 to sum as digit 3 occurs in all numbers
// from 300 to 328. The fourth term recursively
// calls for 28
return ($msd * $a[$d] + ($msd * (int)($msd - 1) / 2) * $p +
$msd * (1 + $n % $p) + sumOfDigitsFrom1ToN($n % $p));
}
// Driver Code
$n = 328;
echo ("Sum of digits in numbers " ),
"from 1 to " , $n , " is ",
sumOfDigitsFrom1ToN($n);
// This code is contributed by Sachin
?>
Javascript
<script>
// Javascript program to compute sum of digits
// in numbers from 1 to n
// Function to computer sum of digits in
// numbers from 1 to n. Comments use
// example of 328 to explain the code
function sumOfDigitsFrom1ToN(n)
{
// base case: if n<10 return sum of
// first n natural numbers
if (n < 10)
return (n * (n + 1) / 2);
// d = number of digits minus one in
// n. For 328, d is 2
let d = parseInt(Math.log(n) / Math.log(10), 10);
// computing sum of digits from 1 to 10^d-1,
// d=1 a[0]=0;
// d=2 a[1]=sum of digit from 1 to 9 = 45
// d=3 a[2]=sum of digit from 1 to 99 =
// a[1]*10 + 45*10^1 = 900
// d=4 a[3]=sum of digit from 1 to 999 =
// a[2]*10 + 45*10^2 = 13500
let a = new Array(d+1);
a[0] = 0; a[1] = 45;
for (let i = 2; i <= d; i++)
a[i] = a[i-1] * 10 + 45 *
parseInt(Math.ceil(Math.pow(10, i-1)), 10);
// computing 10^d
let p = parseInt(Math.ceil(Math.pow(10, d)), 10);
// Most significant digit (msd) of n,
// For 328, msd is 3 which can be obtained
// using 328/100
let msd = parseInt(n / p, 10);
// EXPLANATION FOR FIRST and SECOND TERMS IN
// BELOW LINE OF CODE
// First two terms compute sum of digits from
// 1 to 299
// (sum of digits in range 1-99 stored in a[d]) +
// (sum of digits in range 100-199, can be
// calculated as 1*100 + a[d]
// (sum of digits in range 200-299, can be
// calculated as 2*100 + a[d]
// The above sum can be written as 3*a[d] +
// (1+2)*100
// EXPLANATION FOR THIRD AND FOURTH TERMS IN
// BELOW LINE OF CODE
// The last two terms compute sum of digits in
// number from 300 to 328. The third term adds
// 3*29 to sum as digit 3 occurs in all numbers
// from 300 to 328. The fourth term recursively
// calls for 28
return (msd * a[d] + (msd * (msd - 1) / 2) * p +
msd * (1 + n % p) + sumOfDigitsFrom1ToN(n % p));
}
let n = 328;
document.write("Sum of digits in numbers from 1 to " + n +
" is " + sumOfDigitsFrom1ToN(n));
</script>
Producción
Sum of digits in numbers from 1 to 328 is 3241
Complejidad temporal: O((len(N)) 2 )
Espacio auxiliar: O(len(N))
El algoritmo eficiente tiene una ventaja más: necesitamos calcular la array ‘a[]’ solo una vez, incluso cuando se nos dan varias entradas.
Mejora: la implementación anterior toma tiempo O (d 2 ) ya que cada llamada recursiva calcula la array dp [] una vez más. La primera llamada toma O(d), la segunda llamada toma O(d-1), la tercera llamada O(d-2), y así sucesivamente. No necesitamos volver a calcular la array dp[] en cada llamada recursiva. A continuación se muestra la implementación modificada que funciona en tiempo O(d). Donde d es un número de dígitos en el número de entrada.
C++
// C++ program to compute sum of digits
// in numbers from 1 to n
#include<bits/stdc++.h>
using namespace std;
int sumOfDigitsFrom1ToNUtil(int n, int a[])
{
if (n < 10)
return (n * (n + 1) / 2);
int d = (int)(log10(n));
int p = (int)(ceil(pow(10, d)));
int msd = n / p;
return (msd * a[d] + (msd * (msd - 1) / 2) * p +
msd * (1 + n % p) +
sumOfDigitsFrom1ToNUtil(n % p, a));
}
// Function to computer sum of digits in
// numbers from 1 to n
int sumOfDigitsFrom1ToN(int n)
{
int d = (int)(log10(n));
int a[d + 1];
a[0] = 0; a[1] = 45;
for(int i = 2; i <= d; i++)
a[i] = a[i - 1] * 10 + 45 *
(int)(ceil(pow(10, i - 1)));
return sumOfDigitsFrom1ToNUtil(n, a);
}
// Driver code
int main()
{
int n = 328;
cout << "Sum of digits in numbers from 1 to "
<< n << " is "<< sumOfDigitsFrom1ToN(n);
}
// This code is contributed by ajaykr00kj
Java
// JAVA program to compute sum of digits
// in numbers from 1 to n
import java.io.*;
import java.math.*;
class GFG{
// Function to computer sum of digits in
// numbers from 1 to n
static int sumOfDigitsFrom1ToN(int n)
{
int d = (int)(Math.log10(n));
int a[] = new int[d+1];
a[0] = 0; a[1] = 45;
for (int i = 2; i <= d; i++)
a[i] = a[i-1] * 10 + 45 *
(int)(Math.ceil(Math.pow(10, i-1)));
return sumOfDigitsFrom1ToNUtil(n, a);
}
static int sumOfDigitsFrom1ToNUtil(int n, int a[])
{
if (n < 10)
return (n * (n + 1) / 2);
int d = (int)(Math.log10(n));
int p = (int)(Math.ceil(Math.pow(10, d)));
int msd = n / p;
return (msd * a[d] + (msd * (msd - 1) / 2) * p +
msd * (1 + n % p) + sumOfDigitsFrom1ToNUtil(n % p, a));
}
// Driver Program
public static void main(String args[])
{
int n = 328;
System.out.println("Sum of digits in numbers " +
"from 1 to " +n + " is " +
sumOfDigitsFrom1ToN(n));
}
}
/*This code is contributed by Narendra Jha.*/
Python3
# Python program to compute sum of digits
# in numbers from 1 to n
import math
# Function to computer sum of digits in
# numbers from 1 to n
def sumOfDigitsFrom1ToN(n):
d = int(math.log(n, 10))
a = [0]*(d + 1)
a[0] = 0
a[1] = 45
for i in range(2, d + 1):
a[i] = a[i - 1] * 10 + 45 * \
int(math.ceil(pow(10, i - 1)))
return sumOfDigitsFrom1ToNUtil(n, a)
def sumOfDigitsFrom1ToNUtil(n, a):
if (n < 10):
return (n * (n + 1)) // 2
d = int(math.log(n,10))
p = int(math.ceil(pow(10, d)))
msd = n // p
return (msd * a[d] + (msd * (msd - 1) // 2) * p +
msd * (1 + n % p) + sumOfDigitsFrom1ToNUtil(n % p, a))
# Driver code
n = 328
print("Sum of digits in numbers from 1 to",n,"is",sumOfDigitsFrom1ToN(n))
# This code is contributed by shubhamsingh10
C#
// C# program to compute sum of digits
// in numbers from 1 to n
using System;
class GFG
{
// Function to computer sum of digits in
// numbers from 1 to n
static int sumOfDigitsFrom1ToN(int n)
{
int d = (int)(Math.Log10(n));
int []a = new int[d+1];
a[0] = 0; a[1] = 45;
for (int i = 2; i <= d; i++)
a[i] = a[i-1] * 10 + 45 *
(int)(Math.Ceiling(Math.Pow(10, i-1)));
return sumOfDigitsFrom1ToNUtil(n, a);
}
static int sumOfDigitsFrom1ToNUtil(int n, int []a)
{
if (n < 10)
return (n * (n + 1) / 2);
int d = (int)(Math.Log10(n));
int p = (int)(Math.Ceiling(Math.Pow(10, d)));
int msd = n / p;
return (msd * a[d] + (msd * (msd - 1) / 2) * p +
msd * (1 + n % p) + sumOfDigitsFrom1ToNUtil(n % p, a));
}
// Driver code
public static void Main(String []args)
{
int n = 328;
Console.WriteLine("Sum of digits in numbers " +
"from 1 to " +n + " is " +
sumOfDigitsFrom1ToN(n));
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to compute sum of digits
// in numbers from 1 to n
// Function to computer sum of digits in
// numbers from 1 to n
function sumOfDigitsFrom1ToNUtil( n,a)
{
if (n < 10)
return (n * (n + 1) / 2);
var d = (parseInt)(Math.log10(n));
var p = (Math.ceil(Math.pow(10, d)));
var msd =(parseInt) (n / p);
return (msd * a[d] + (msd * (msd - 1) / 2) * p +
msd * (1 + n % p) +
sumOfDigitsFrom1ToNUtil(n % p, a));
}
// Function to computer sum of digits in
// numbers from 1 to n
function sumOfDigitsFrom1ToN( n)
{
var d =(parseInt)(Math.log10(n));
var a=new Array(d + 1).fill(0);
a[0] = 0; a[1] = 45;
for(var i = 2; i <= d; i++)
a[i] = a[i - 1] * 10 + 45 *
(parseInt)(Math.ceil(Math.pow(10, i - 1)));
return sumOfDigitsFrom1ToNUtil(n, a);
}
var n = 328;
document.write( "Sum of digits in numbers from 1 to "
+ n + " is "+ sumOfDigitsFrom1ToN(n))
</script>
Producción
Sum of digits in numbers from 1 to 328 is 3241
Complejidad temporal: O(len(N))
Espacio auxiliar: O(len(N))
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA