Dados tres enteros A , B y N . La tarea es encontrar la suma de todos los elementos debajo de N que son múltiplos de A o B.
Ejemplos:
Entrada: N = 10, A = 3, B = 5
Salida: 23
3, 5, 6 y 9 son los únicos números debajo de 10 que son múltiplos de 3 o 5Entrada: N = 50, A = 8, B = 15
Salida: 258
Enfoque ingenuo:
- Inicializa una variable sum = 0 .
- Bucle de 0 a n para cada i verifique si i % A = 0 o i % B = 0 .
- Si se cumple la condición anterior, actualice sum = sum + i .
- Finalmente devuelve la suma .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the
// sum of all the integers
// below N which are multiples
// of either A or B
#include <iostream>
using namespace std;
// Function to return the
// sum of all the integers
// below N which are multiples
// of either A or B
int findSum(int n, int a, int b)
{
int sum = 0;
for (int i = 0; i < n; i++)
// If i is a multiple of a or b
if (i % a == 0 || i % b == 0)
sum += i;
return sum;
}
// Driver code
int main()
{
int n = 10, a = 3, b = 5;
cout << findSum(n, a, b);
return 0;
}
C
// C program for above approach
#include <stdio.h>
// Function to return the
// sum of all the integers
// below N which are multiples
// of either A or B
int findSum(int n, int a, int b)
{
int sum = 0;
for (int i = 0; i < n; i++)
// If i is a multiple of a or b
if (i % a == 0 || i % b == 0)
sum += i;
return sum;
}
// Driver Code
int main()
{
int n = 10, a = 3, b = 5;
printf("%d",findSum(n, a, b));
return 0;
}
//This code is contributed by Shivshanker Singh
Java
// Java program to find the
// sum of all the integers
// below N which are multiples
// of either A or B
import java.io.*;
class GFG
{
// Function to return the
// sum of all the integers
// below N which are multiples
// of either A or B
static int findSum(int n, int a, int b)
{
int sum = 0;
for (int i = 0; i < n; i++)
// If i is a multiple of a or b
if (i % a == 0 || i % b == 0)
sum += i;
return sum;
}
// Driver code
public static void main(String[] args)
{
int n = 10, a = 3, b = 5;
System.out.println(findSum(n, a, b));
}
}
// This code is contributed by anuj_67..
Python3
# Python 3 program to find the sum of # all the integers below N which are # multiples of either A or B # Function to return the sum of all # the integers below N which are # multiples of either A or B def findSum(n, a, b): sum = 0 for i in range(0, n, 1): # If i is a multiple of a or b if (i % a == 0 or i % b == 0): sum += i return sum # Driver code if __name__ == '__main__': n = 10 a = 3 b = 5 print(findSum(n, a, b)) # This code is contributed by # Surendra_Gangwar
C#
// C# program to find the sum
// of all the integers
// below N which are multiples
// of either A or B
using System;
class GFG
{
// Function to return the sum
// of all the integers
// below N which are multiples
// of either A or B
static int findSum(int n, int a, int b)
{
int sum = 0;
for (int i = 0; i < n; i++)
// If i is a multiple of a or b
if (i % a == 0 || i % b == 0)
sum += i;
return sum;
}
// Driver code
static void Main()
{
int n = 10, a = 3, b = 5;
Console.WriteLine(findSum(n, a, b));
}
// This code is contributed by Ryuga
}
PHP
<?php
// PHP program to find the sum of all
// the integers below N which are
// multiples of either A or B
// Function to return the sum of all
// the integers below N which are
// multiples of either A or B
function findSum($n, $a, $b)
{
$sum = 0;
for ($i = 0; $i < $n; $i++)
// If i is a multiple of a or b
if ($i % $a == 0 || $i % $b == 0)
$sum += $i;
return $sum;
}
// Driver code
$n = 10;
$a = 3;
$b = 5;
echo findSum($n, $a, $b);
// This code is contributed by Sachin
?>
Javascript
<script>
// Javascript program to find the sum of all
// the integers below N which are multiples
// of either A or B
// Function to return the sum of all
// the integers below N which are
// multiples of either A or B
function findSum(n, a, b)
{
let sum = 0;
for(let i = 0; i < n; i++)
// If i is a multiple of a or b
if (i % a == 0 || i % b == 0)
sum += i;
return sum;
}
// Driver code
let n = 10;
let a = 3;
let b = 5;
document.write( findSum(n, a, b));
// This code is contributed by mohan
</script>
Producción:
23
Complejidad Temporal: O(N), ya que el ciclo va de 0 a (n – 1).
Espacio Auxiliar: O(1), ya que no se ha ocupado ningún espacio extra.
Enfoque eficiente:
Para una mejor comprensión de un enfoque eficiente, comencemos desde cero.
Tenemos los números = 1, 2, 3, 4, ………. , N-1 , Norte
Todos los números divisibles por A = A, 2A, 3A, ………….. ⌊N/A⌋*A
Llamemos a esto, sum1 =A + 2A + 3A+ …………..+ ⌊N/A⌋*A
suma1 = A(1 + 2 + 3+ …………..+ ⌊N/A⌋ )
suma1 = A* ⌊N/A⌋ * ( ⌊N/A⌋ + 1 )/2
Donde ⌊ ⌋ es la función base (o Mínimo entero).
y se utiliza la fórmula de suma de n números naturales n*(n+1)/2.
Del mismo modo suma de números divisible por B –
suma2 =B* ⌊N/B⌋ *( ⌊N/B⌋ + 1 )/2
Entonces total sum = sum1 + sum2 pero puede haber números de suma que serán comunes en ambos,
Por ejemplo, sea N=10, A=2, B=3
Entonces suma1 = 2+4+6+8+10+12+14+16+18+20
suma2 = 3+6+9+12+15+18
Podemos ver claramente que los números 6, 12, 18 se repiten y todos los demás números son múltiplos de 6, que es el MCM de A y B.
Sea mcm = mcm de A y B
suma3 =mcm* ⌊N/mcm⌋ * ( ⌊N/mcm⌋ + 1 )/2
Por fin podemos calcular la suma usando
suma = suma1 + suma2 – suma3
podemos calcular el MCM usando
mcm = (A*B)/mcd
donde mcd = mcd de A y B
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the
// sum of all the integers
// below N which are multiples
// of either A or B
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
// Function to find sum of AP series
long long sumAP(long long n, long long d)
{
// Number of terms
n /= d;
return (n) * (1 + n) * d / 2;
}
// Function to find the sum of all
// multiples of a and b below n
long long sumMultiples(long long n, long long a,
long long b)
{
// Since, we need the sum of
// multiples less than N
n--;
long lcm = (a*b)/__gcd(a,b);
return sumAP(n, a) + sumAP(n, b) -
sumAP(n, lcm);
}
// Driver code
int main()
{
long long n = 10, a = 3, b = 5;
cout << sumMultiples(n, a, b);
return 0;
}
// This code is Modified by Shivshanker Singh.
C
// C program to find the
// sum of all the integers
// below N which are multiples
// of either A or B
#include <stdio.h>
// Function to find sum of AP series
long long sumAP(long long n, long long d)
{
// Number of terms
n /= d;
return (n) * (1 + n) * d / 2;
}
// Function to find the gcd of A and B.
long gcd(int p, int q)
{
if (p == 0)
return q;
return gcd(q % p, p);
}
// Function to find the sum of all
// multiples of a and b below n
long long sumMultiples(long long n, long long a,
long long b)
{
// Since, we need the sum of
// multiples less than N
n--;
long lcm = (a*b)/gcd(a,b);
return sumAP(n, a) + sumAP(n, b) - sumAP(n, lcm);
}
// Driver code
int main()
{
long long n = 10, a = 3, b = 5;
printf("%lld", sumMultiples(n, a, b));
return 0;
}
// This code is Contributed by Shivshanker Singh.
Java
// Java program to find the
// sum of all the integers
// below N which are multiples
// of either A or B
import java.io.*;
class GFG
{
// Function to find sum of AP series
static long sumAP(long n, long d)
{
// Number of terms
n = (int)n / d;
return (n) * (1 + n) * d / 2;
}
// Function to find gcd of A and B
public static long gcd(long p, long q)
{
if (p == 0)
return q;
return gcd(q % p, p);
}
// Function to find the sum of all
// multiples of a and b below n
static long sumMultiples(long n, long a,
long b)
{
// Since, we need the sum of
// multiples less than N
n--;
long lcm = (a * b) / gcd(a, b);
return sumAP(n, a) + sumAP(n, b) -
sumAP(n, lcm);
}
// Driver code
public static void main(String[] args)
{
long n = 10, a = 3, b = 5;
System.out.println(sumMultiples(n, a, b));
}
// This code is Modified by Shivshanker Singh.
}
Python3
import math # Python3 program to find the sum of # all the integers below N which are # multiples of either A or B # Function to find sum of AP series def sumAP(n, d): # Number of terms n = n//d return (n) * (1 + n) * d // 2 # Function to find the sum of all # multiples of a and b below n def sumMultiples(n, a, b): # Since, we need the sum of # multiples less than N n = n-1 lcm = (a*b)//math.gcd(a, b) return sumAP(n, a) + sumAP(n, b) - \ sumAP(n, lcm) # Driver code n = 10 a = 3 b = 5 print(sumMultiples(n, a, b)) # This code is Modified by Shivshanker Singh.
C#
// C# program to find the
// sum of all the integers
// below N which are multiples
// of either A or B
using System;
public class GFG
{
// Function to find sum of AP series
static long sumAP(long n, long d)
{
// Number of terms
n = (int)n / d;
return (n) * (1 + n) * d / 2;
}
// Function to find gcd of A and B
static long gcd(long p, long q)
{
if (p == 0)
return q;
return gcd(q % p, p);
}
// Function to find the sum of all
// multiples of a and b below n
static long sumMultiples(long n, long a,
long b)
{
// Since, we need the sum of
// multiples less than N
n--;
long lcm = (a * b) / gcd(a, b);
return sumAP(n, a) + sumAP(n, b) -
sumAP(n, lcm);
}
// Driver code
static public void Main()
{
long n = 10, a = 3, b = 5;
Console.WriteLine(sumMultiples(n, a, b));
}
// This code is Modified by Shivshanker Singh.
}
PHP
<?php
// PHP program to find the
// sum of all the integers
// below N which are multiples
// of either A or B
// Function to find sum of AP series
function sumAP( $n, $d)
{
// Number of terms
$n = (int)($n / $d);
return ($n) * (1 + $n) * $d / 2;
}
// Function to find the sum of all
// multiples of a and b below n
function sumMultiples( $n, $a, $b)
{
// Since, we need the sum of
// multiples less than N
$n--;
return sumAP($n, $a) + sumAP($n, $b) -
sumAP($n, $a * $b);
}
// Driver code
{
$n = 10;
$a = 3;
$b = 5;
echo(sumMultiples($n, $a, $b));
return 0;
}
//This code is contributed by Shivshanker Singh
Javascript
<script>
// Javascript program to find the
// sum of all the integers
// below N which are multiples
// of either A or B
// Function to find sum of AP series
function sumAP(n, d)
{
// Number of terms
n = parseInt(n / d);
return (n) * (1 + n) * d / 2;
}
// Function to find gcd of A and B
function gcd(p, q)
{
if (p == 0)
return q;
return gcd(q % p, p);
}
// Function to find the sum of all
// multiples of a and b below n
function sumMultiples(n, a, b)
{
// Since, we need the sum of
// multiples less than N
n--;
var lcm = (a * b) / gcd(a, b);
return sumAP(n, a) + sumAP(n, b) -
sumAP(n, lcm);
}
// Driver code
{
let n = 10;
let a = 3;
let b = 5;
document.write(sumMultiples(n, a, b));
}
// This code is contributed by mohan
</script>
Producción:
23
Complejidad del tiempo: O(log(N))
Espacio Auxiliar: O(1)