Suma de múltiplos de elementos de Array dentro de un rango dado [L, R]

Posted on by Rudeus Greyrat

Dada una array arr[] de enteros positivos y dos enteros L y R , la tarea es encontrar la suma de todos los múltiplos de los elementos de la array en el rango [L, R] .

Ejemplos: 

Entrada: arr[] = {2, 7, 3, 8}, L = 7, R = 20 
Salida: 197 
Explicación: 
En el rango de 7 a 20: 
Suma de múltiplos de 2: 8 + 10 + 12 + 14 + 16 + 18 + 20 = 98 
Suma de múltiplos de 7: 7 + 14 = 21 
Suma de múltiplos de 3: 9 + 12 + 15 + 18 = 54 
Suma de múltiplos de 8: 8 + 16 = 24 
Suma total de todos los múltiplos = 98 + 21 + 54 + 24 = 197

Entrada: arr[] = {5, 6, 7, 8, 9}, L = 39, R = 100 
Salida: 3278 

Enfoque ingenuo: la idea ingenua es que para cada elemento en la array dada arr[] encuentre el múltiplo del elemento en el rango [L, R] e imprima la suma de todos los múltiplos.

Complejidad temporal: O(N*(LR)) 
Espacio auxiliar: O(1)

Enfoque eficiente: para optimizar el enfoque ingenuo anterior, utilizaremos el concepto que se analiza a continuación: 

  1. Para cualquier entero X , el número de múltiplos de X hasta cualquier entero Y está dado por Y/X .
  2. Sea N = Y/X 
    Entonces, la suma de todos los múltiplos anteriores está dada por X*N*(N-1)/2 .

Por ejemplo: 

Para X = 2 e Y = 12 La 
suma del múltiplo es: 
=> 2 + 4 + 6 + 8 + 10 + 12 
=> 2*(1 + 2 + 3 + 4 + 5 + 6) 
=> 2*(6* 5)/2 
=> 20. 

Usando el concepto anterior, el problema se puede resolver usando los siguientes pasos: 

  1. Calcule la suma de todos los múltiplos de arr[i] hasta R usando la fórmula mencionada anteriormente.
  2. Calcule la suma de todos los múltiplos de arr[i] hasta L – 1 usando la fórmula discutida anteriormente.
  3. Reste los dos valores anteriores en los pasos anteriores para obtener la suma de todos los múltiplos entre rangos [L, R] .
  4. Repita el proceso anterior para todos los elementos e imprima la suma.

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

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the sum of all
// multiples of N up to K
int calcSum(int k, int n)
{
    // Calculate the sum
    int value = (k * n * (n
                          + 1))
                / 2;
    // Return the sum
    return value;
}
 
// Function to find the total sum
int findSum(int* a, int n, int L, int R)
{
    int sum = 0;
    for (int i = 0; i < n; i++) {
 
        // Calculating sum of multiples
        // for each element
 
        // If L is divisible by a[i]
        if (L % a[i] == 0 && L != 0) {
            sum += calcSum(a[i], R / a[i])
                   - calcSum(a[i],
                             (L - 1) / a[i]);
        }
 
        // Otherwise
        else {
            sum += calcSum(a[i], R / a[i])
                   - calcSum(a[i], L / a[i]);
        }
    }
 
    // Return the final sum
    return sum;
}
 
// Driver Code
int main()
{
    // Given array arr[]
    int arr[] = { 2, 7, 3, 8 };
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Given range
    int L = 7;
    int R = 20;
 
    // Function Call
    cout << findSum(arr, N, L, R);
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
 
class GFG{
     
// Function to find the sum of
// all multiples of N up to K
static int calcSum(int k, int n)
{
     
    // Calculate the sum
    int value = (k * n * (n + 1)) / 2;
     
    // Return the sum
    return value;
}
 
// Function to find the total sum
static int findSum(int[] a, int n,
                   int L, int R)
{
    int sum = 0;
    for(int i = 0; i < n; i++)
    {
        
       // Calculating sum of multiples
       // for each element
        
       // If L is divisible by a[i]
       if (L % a[i] == 0 && L != 0)
       {
           sum += calcSum(a[i], R / a[i]) -
                  calcSum(a[i], (L - 1) / a[i]);
       }
        
       // Otherwise
       else
       {
           sum += calcSum(a[i], R / a[i]) -
                  calcSum(a[i], L / a[i]);
       }
    }
 
    // Return the final sum
    return sum;
}
 
// Driver Code
public static void main (String[] args)
{
     
    // Given array arr[]
    int arr[] = { 2, 7, 3, 8 };
 
    int N = arr.length;
 
    // Given range
    int L = 7;
    int R = 20;
 
    // Function Call
    System.out.println(findSum(arr, N, L, R));
}
}
 
// This code is contributed by shubhamsingh10

Python3

# Python3 program for the above approach
 
# Function to find the sum of
# all multiples of N up to K
def calcSum(k, n):
 
    # Calculate the sum
    value = (k * n * (n + 1)) // 2
     
    # Return the sum
    return value
     
# Function to find the total sum
def findSum(a, n, L, R):
 
    sum = 0
    for i in range(n):
         
        # Calculating sum of multiples
        # for each element
         
        # If L is divisible by a[i]
        if (L % a[i] == 0 and L != 0):
            sum += (calcSum(a[i], R // a[i]) -
                    calcSum(a[i], (L - 1) // a[i]))
         
        # Otherwise
        else:
            sum += (calcSum(a[i], R // a[i]) -
                    calcSum(a[i], L // a[i]))
     
    # Return the final sum
    return sum;
 
# Driver code
if __name__=="__main__":
     
    # Given array arr[]
    arr = [ 2, 7, 3, 8 ]
 
    N = len(arr)
 
    # Given range
    L = 7
    R = 20
 
    # Function call
    print(findSum(arr, N, L, R))    
 
# This code is contributed by rutvik_56

C#

// C# program for the above approach
using System;
class GFG{
      
// Function to find the sum of
// all multiples of N up to K
static int calcSum(int k, int n)
{
      
    // Calculate the sum
    int value = (k * n * (n + 1)) / 2;
      
    // Return the sum
    return value;
}
  
// Function to find the total sum
static int findSum(int[] a, int n,
                   int L, int R)
{
    int sum = 0;
    for(int i = 0; i < n; i++)
    {
         
       // Calculating sum of multiples
       // for each element
         
       // If L is divisible by a[i]
       if (L % a[i] == 0 && L != 0)
       {
           sum += calcSum(a[i], R / a[i]) -
                  calcSum(a[i], (L - 1) / a[i]);
       }
         
       // Otherwise
       else
       {
           sum += calcSum(a[i], R / a[i]) -
                  calcSum(a[i], L / a[i]);
       }
    }
  
    // Return the final sum
    return sum;
}
  
// Driver Code
public static void Main (string[] args)
{
      
    // Given array arr[]
    int []arr = new int[]{ 2, 7, 3, 8 };
  
    int N = arr.Length;
  
    // Given range
    int L = 7;
    int R = 20;
  
    // Function Call
    Console.Write(findSum(arr, N, L, R));
}
}
  
// This code is contributed by Ritik Bansal

Javascript

<script>
// Javascript implementation for the above approach
 
// Function to find the sum of
// all multiples of N up to K
function calcSum(k, n)
{
     
    // Calculate the sum
    let value = (k * n * (n + 1)) / 2;
     
    // Return the sum
    return value;
}
 
// Function to find the total sum
function findSum(a, n, L, R)
{
    let sum = 0;
    for(let i = 0; i < n; i++)
    {
        
       // Calculating sum of multiples
       // for each element
        
       // If L is divisible by a[i]
       if (L % a[i] == 0 && L != 0)
       {
           sum += calcSum(a[i], Math.floor(R / a[i])) -
                  calcSum(a[i], Math.floor((L - 1) / a[i]));
       }
        
       // Otherwise
       else
       {
           sum += calcSum(a[i], Math.floor(R / a[i])) -
                  calcSum(a[i], Math.floor(L / a[i]));
       }
    }
 
    // Return the final sum
    return sum;
}
 
    // Driver Code
     
    // Given array arr[]
    let arr = [ 2, 7, 3, 8 ];
 
    let N = arr.length;
 
    // Given range
    let L = 7;
    let R = 20;
 
    // Function Call
   document.write(findSum(arr, N, L, R));
         
</script>
Producción: 

197

 

Complejidad de tiempo: O(N), donde N es el número de elementos en la array dada. 
Espacio Auxiliar: O(1)
 

Publicación traducida automáticamente

Artículo escrito por AmanGupta65 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *