Suma de enteros hasta N con dígito de unidad dado (Conjunto 2)

Dados dos enteros N y D donde 1 ≤ N ≤ 10 ¹⁸ , la tarea es encontrar la suma de todos los enteros del 1 al N cuya unidad es D .
Ejemplos: 
 

Entrada: N = 30, D = 3 
Salida: 39 
3 + 13 + 23 = 39
Entrada: N = 5, D = 7 
Salida: 0 
 

Enfoque: En el Conjunto 1 vimos dos enfoques básicos para encontrar la suma requerida, pero la complejidad es O(N) , lo que llevará más tiempo para N más grandes . Aquí hay un enfoque incluso eficiente, supongamos que nos dan N = 30 y D = 3 : 
 

suma = 3 + 13 + 23 
suma = 3 + (10 + 3) + (20 + 3) 
suma = 3 * (3) + (10 + 20) 
 

De la observación anterior, podemos encontrar la suma siguiendo los pasos a continuación: 
 

• Decrementar N hasta N % 10 != D .
• Encuentre K = N / 10 .
• Ahora suma = (K + 1) * D + (((K * 10) + (10 * K * K)) / 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 ll long long int
 
// Function to return the required sum
ll getSum(ll n, int d)
{
    if (n < d)
        return 0;
 
    // Decrement N
    while (n % 10 != d)
        n--;
 
    ll k = n / 10;
 
    return (k + 1) * d + (k * 10 + 10 * k * k) / 2;
}
 
// Driver code
int main()
{
    ll n = 30;
    int d = 3;
    cout << getSum(n, d);
    return 0;
}

// Java  implementation of the approach
 
import java.io.*;
 
class GFG {
 
 
// Function to return the required sum
static long getSum(long n, int d)
{
    if (n < d)
        return 0;
 
    // Decrement N
    while (n % 10 != d)
        n--;
 
    long k = n / 10;
 
    return (k + 1) * d + (k * 10 + 10 * k * k) / 2;
}
 
// Driver code
 
    public static void main (String[] args) {
     long n = 30;
    int d = 3;
    System.out.println(getSum(n, d));    }
}
//This code is contributed by inder_verma..

# Python3 implementation of the approach
 
# Function to return the required sum
def getSum(n, d) :
     
    if (n < d) :
        return 0
 
    # Decrement N
    while (n % 10 != d) :
        n -= 1
 
    k = n // 10
 
    return ((k + 1) * d +
            (k * 10 + 10 * k * k) // 2)
 
# Driver code
if __name__ == "__main__" :
 
    n = 30
    d = 3
    print(getSum(n, d))
 
# This code is contributed by Ryuga

// C# implementation of the approach
 
 
class GFG {
 
 
// Function to return the required sum
static int getSum(int n, int d)
{
    if (n < d)
        return 0;
 
    // Decrement N
    while (n % 10 != d)
        n--;
 
    int k = n / 10;
 
    return (k + 1) * d + (k * 10 + 10 * k * k) / 2;
}
 
// Driver code
 
    public static void Main () {
    int n = 30;
    int d = 3;
    System.Console.WriteLine(getSum(n, d)); }
}
//This code is contributed by mits.

<?php
// PHP implementation of the approach
 
// Function to return the required sum
function getSum($n, $d)
{
    if ($n < $d)
        return 0;
 
    // Decrement N
    while ($n % 10 != $d)
        $n--;
 
    $k = (int)($n / 10);
 
    return ($k + 1) * $d +
           ($k * 10 + 10 * $k * $k) / 2;
}
 
// Driver code
$n = 30;
$d = 3;
echo getSum($n, $d);
 
// This code is contributed by mits
?>

<script>
 
// java script  implementation of the approach
 
// Function to return the required sum
function getSum(n, d)
{
    if (n < d)
        return 0;
 
    // Decrement N
    while (n % 10 != d)
        n--;
 
    k = parseInt(n / 10);
 
    return (k + 1) * d +
        (k * 10 + 10 * k * k) / 2;
}
 
// Driver code
let n = 30;
let d = 3;
document.write( getSum(n, d));
 
// This code is contributed
// by bobby
</script>

39

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(1)