Suma máxima posible de K incluso múltiplos de 5 en un rango dado

Dados tres números enteros L, R y K , la tarea es encontrar la suma máxima de K incluso múltiplos de 5 del rango [L, R] .

Ejemplos: 

Entrada: L = 7, R = 48, K = 3
Salida: 90
Explicación: Suma máxima de 3 incluso múltiplos de 5 en el rango [7, 48] = 40 + 30 + 20 = 90

Entrada: L = 16, R= 60, K = 4
Salida: 180
Explicación: Suma máxima de 4 múltiplos pares de 5 en el rango [16, 60] = 60 + 50 + 40 + 30 = 180

Enfoque ingenuo: el enfoque más simple es iterar sobre todos los elementos pares de R a L , y para cada elemento, verificar si es divisible por 5 o no . Si se determina que es cierto, agregue ese elemento a la suma y disminuya K . Cuando K llegue a 0, rompa el bucle e imprima la suma obtenida. 

Complejidad de Tiempo: O(N), donde N=RL
Espacio Auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar en función de la siguiente observación: 

Recuento de múltiplos pares de 5 en el rango [1, X] = X / 10
Recuento de múltiplos pares de 5 en el rango [L, R] = (R / 10 – L / 10) + 1 = N (digamos)
Suma máxima de K múltiplos pares de 5 en el rango [L, R] 
= Suma de múltiplos pares de 5 en el rango [1, R] – Suma de múltiplos pares de 5 en el rango [1, R – K]
= 10 * (N * ( N + 1) / 2 – M * (M + 1) / 2), donde M = R – K

Siga los pasos a continuación para resolver el problema: 

• Inicialice N = (R / 10 – L / 10) + 1 para almacenar el conteo de múltiplos pares de 5 en el rango [L, R] .
• Si K > N , imprima -1 indicando que hay menos de K múltiplos pares de 5 en el rango [L, R] .
• De lo contrario:
  • Inicializar M = R – K .
  • Almacenar suma = 10 * (N * (N + 1) / 2 – M * (M + 1) / 2) .
  • Imprimir suma .

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

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum sum of K
// even multiples of 5 in the range [L, R]
void maxksum(int L, int R, int K)
{
    // Store the total number of even
    // multiples of 5 in the range [L, R]
    int N = (R / 10 - L / 10) + 1;
 
    // Check if K > N
    if (K > N) {
 
        // If true, print -1 and return
        cout << -1;
        return;
    }
 
    // Otherwise, divide R by 10
    R = R / 10;
 
    // Store the sum using the formula
    int X = R - K;
    int sum = 10 * ((R * (R + 1)) / 2
                    - (X * (X + 1)) / 2);
 
    // Print the sum
    cout << sum;
}
 
// Driver Code
int main()
{
 
    // Given L, R and K
    int L = 16, R = 60, K = 4;
 
    // Function Call
    maxksum(L, R, K);
 
    return 0;
}

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
     
// Function to find the maximum sum of K
// even multiples of 5 in the range [L, R]
static void maxksum(int L, int R, int K)
{
     
    // Store the total number of even
    // multiples of 5 in the range [L, R]
    int N = (R / 10 - L / 10) + 1;
 
    // Check if K > N
    if (K > N)
    {
         
        // If true, print -1 and return
        System.out.print("-1");
        return;
    }
     
    // Otherwise, divide R by 10
    R = R / 10;
 
    // Store the sum using the formula
    int X = R - K;
    int sum = 10 * ((R * (R + 1)) / 2 -
                    (X * (X + 1)) / 2);
 
    // Print the sum
    System.out.print( sum);
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given L, R and K
    int L = 16, R = 60, K = 4;
     
    // Function Call
    maxksum(L, R, K);
}
}
 
// This code is contributed by Stream_Cipher

# Python3 program to implement
# the above approach
 
# Function to find the maximum sum of K
# even multiples of 5 in the range [L, R]
def maxksum(L, R, K) :
 
    # Store the total number of even
    # multiples of 5 in the range [L, R]
    N = (R // 10 - L // 10) + 1;
 
    # Check if K > N
    if (K > N) :
 
        # If true, print -1 and return
        print(-1);
        return;
 
    # Otherwise, divide R by 10
    R = R // 10;
 
    # Store the sum using the formula
    X = R - K;
    sum = 10 * ((R * (R + 1)) // 2 - (X * (X + 1)) // 2);
 
    # Print the sum
    print(sum);
 
# Driver Code
if __name__ == "__main__" :
 
    # Given L, R and K
    L = 16; R = 60; K = 4;
 
    # Function Call
    maxksum(L, R, K);
 
    # This code is contributed by AnkThon

// C# program to implement
// the above approach 
using System;
class GFG
{
  
// Function to find the maximum sum of K
// even multiples of 5 in the range [L, R]
static void maxksum(int L, int R, int K)
{
      
    // Store the total number of even
    // multiples of 5 in the range [L, R]
    int N = (R / 10 - L / 10) + 1;
  
    // Check if K > N
    if (K > N)
    {
          
        // If true, print -1 and return
        Console.Write("-1");
        return;
    }
      
    // Otherwise, divide R by 10
    R = R / 10;
  
    // Store the sum using the formula
    int X = R - K;
    int sum = 10 * ((R * (R + 1)) / 2 -
                    (X * (X + 1)) / 2);
  
    // Print the sum
    Console.Write( sum);
}
  
// Driver code
public static void Main()
{
   
    // Given L, R and K
    int L = 16, R = 60, K = 4;
      
    // Function Call
    maxksum(L, R, K);
}
}
 
// This code is contributed by sanjoy_62

<script>
 
// Javascript program to implement
// the above approach
 
// Function to find the maximum sum of K
// even multiples of 5 in the range [L, R]
function maxksum(L, R, K)
{
     
    // Store the total number of even
    // multiples of 5 in the range [L, R]
    let N = (R / 10 - L / 10) + 1;
 
    // Check if K > N
    if (K > N)
    {
         
        // If true, print -1 and return
        document.write("-1");
        return;
    }
     
    // Otherwise, divide R by 10
    R = R / 10;
 
    // Store the sum using the formula
    let X = R - K;
    let sum = 10 * ((R * (R + 1)) / 2 -
                    (X * (X + 1)) / 2);
 
    // Print the sum
    document.write(sum);
}
 
// Driver Code
 
// Given L, R and K
let L = 16, R = 60, K = 4;
 
// Function Call
maxksum(L, R, K);
 
// This code is contributed by splevel62
 
</script>

180

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)