Suma de i * countDigits(i)^2 para todos los i en el rango [L, R]

Dado un rango [L, R] , la tarea es encontrar la suma i * countDigits(i) ² para todo i ∈ [L, R] donde countDigits(i) es el conteo de dígitos en i .
Es decir, encuentra: 
 

L * contarDigitos(L) ² + (L + 1) * contarDigitos(L + 1) ² + ….. + R * contarDigitos(R) ² . 
 

Ejemplos: 
 

Entrada: L = 8, R = 11 
Salida: 101 
8 * 1 ² + 9 * 1 ² + 10 * 2 ² + 11 * 2 ² = 8 + 9 + 40 + 44 = 101
Entrada: L = 98, R = 102 
Salida: 2 
98 * 2 ² + 99 * 2 ² + 100 * 3 ² + 101 * 3 ² + 102 * 3 ² = 3515 
 

Enfoque: Partimos el segmento [L, R] en varios segmentos de los números con el mismo número de dígitos. 
[1 – 9], [10 – 99], [100 – 999], [1000 – 9999], [10000 – 99999], [100000 – 999999], [10000000 – 99999999] y así sucesivamente.  
Cuando L y R tienen la misma longitud, la suma requerida será countDigits(L) ² * (L + R) * (R – L + 1) / 2
Prueba: 
 

Sea [L, R] = [10, 14] donde L y R tienen la misma longitud, es decir, 2. 
Por lo tanto, la suma del segmento [L, R] será 10 * 2 ² + 11 * 2 ² + 12 * 2 ² + 13 * 2 ² + 14 * 2 ² . 
Tome 2 ² comunes, 2 ² * (10 + 11 + 12 + 13 + 14) = totalDigits ² * (Suma de AP) 
Suma de AP = (nº de términos / 2) * (primer término + último término) es decir (R – L + 1) * (L + R) / 2 . 
 

A continuación se muestra la implementación del enfoque anterior:
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
 
// Function to return the required sum
int rangeSum(int l, int r)
{
 
    int a = 1, b = 9, res = 0;
    for (int i = 1; i <= 10; i++) {
        int L = max(l, a);
        int R = min(r, b);
 
        // If range is valid
        if (L <= R) {
 
            // Sum of AP
            int sum = (L + R) * (R - L + 1) / 2;
            res += (i * i) * (sum % MOD);
            res %= MOD;
        }
        a = a * 10;
        b = b * 10 + 9;
    }
    return res;
}
 
// Driver code
int main()
{
    int l = 98, r = 102;
    cout << rangeSum(l, r);
 
    return 0;
}

// Java implementation of the approach
class GFG {
 
    static final int MOD = 1000000007;
 
    // Function to return the required sum
    static int rangeSum(int l, int r)
    {
 
        int a = 1, b = 9, res = 0;
        for (int i = 1; i <= 10; i++) {
            int L = Math.max(l, a);
            int R = Math.min(r, b);
 
            // If range is valid
            if (L <= R) {
 
                // Sum of AP
                int sum = (L + R) * (R - L + 1) / 2;
                res += (i * i) * (sum % MOD);
                res %= MOD;
            }
            a = a * 10;
            b = b * 10 + 9;
        }
        return res;
    }
 
    // Driver code
    public static void main(String args[])
    {
 
        int l = 98, r = 102;
        System.out.print(rangeSum(l, r));
    }
}

# Python3 implementation of the approach
 
MOD = 1000000007;
 
# Function to return the required sum
def rangeSum(l, r) :
 
    a = 1; b = 9; res = 0;
    for i in range(1, 11) :
        L = max(l, a);
        R = min(r, b);
         
        # If range is valid
        if (L <= R) :
             
            # Sum of AP
            sum = (L + R) * (R - L + 1) // 2;
            res += (i * i) * (sum % MOD);
            res %= MOD;
         
        a *= 10;
        b = b * 10 + 9;
     
    return res;
 
# Driver code
if __name__ == "__main__" :
 
    l = 98 ; r = 102;
     
    print(rangeSum(l, r));
 
# This code is contributed by Ryuga

// C# implementation of the approach
using System;
class GFG {
 
    const int MOD = 1000000007;
 
    // Function to return the required sum
    static int rangeSum(int l, int r)
    {
 
        int a = 1, b = 9, res = 0;
        for (int i = 1; i <= 10; i++) {
            int L = Math.Max(l, a);
            int R = Math.Min(r, b);
 
            // If range is valid
            if (L <= R) {
 
                // Sum of AP
                int sum = (L + R) * (R - L + 1) / 2;
                res += (i * i) * (sum % MOD);
                res %= MOD;
            }
            a = a * 10;
            b = b * 10 + 9;
        }
        return res;
    }
 
    // Driver code
    public static void Main()
    {
        int l = 98, r = 102;
        Console.WriteLine(rangeSum(l, r));
    }
}

<?php
// PHP implementation of the approach
 
$MOD = 1000000007;
 
// Function to return the required sum
function rangeSum($l, $r)
{
    global $MOD;
    $a = 1; $b = 9; $res = 0;
    for ($i = 1; $i <= 10; $i++)
    {
        $L = max($l, $a);
        $R = min($r, $b);
 
        // If range is valid
        if ($L <= $R)
        {
 
            // Sum of AP
            $sum = ($L + $R) * ($R - $L + 1) / 2;
            $res += ($i * $i) * ($sum % $MOD);
            $res %= $MOD;
        }
        $a = $a * 10;
        $b = $b * 10 + 9;
    }
    return $res;
}
 
// Driver code
$l = 98; $r = 102;
echo rangeSum($l, $r);
 
// This code is contributed
// by Akanksha Rai
?>

<script>
// Javascript implementation of the approach
MOD=1000000007
 
// Function to return the required sum
function rangeSum(l, r)
{
 
    var a = 1, b = 9, res = 0;
    for (var i = 1; i <= 10; i++) {
        var L = Math.max(l, a);
        var R = Math.min(r, b);
 
        // If range is valid
        if (L <= R) {
 
            // Sum of AP
            var sum = (L + R) * (R - L + 1) / 2;
            res += (i * i) * (sum % MOD);
            res %= MOD;
        }
        a = a * 10;
        b = b * 10 + 9;
    }
    return res;
}
 
// Driver code
var l = 98, r = 102;
document.write(rangeSum(l, r));
 
// This code is contributed by noob2000.
</script>

3515

Complejidad de tiempo: O (10), ya que estamos usando un bucle para repetir 10 veces.

Espacio auxiliar: O(1), ya que no estamos usando espacio extra.