Dado un número N. Dados dos números X e Y , la tarea es encontrar la suma de todos aquellos números del 1 al N que son divisibles por X o por Y.
Ejemplos :
Input : N = 20 Output : 98 Input : N = 14 Output : 45
Enfoque : para resolver el problema, siga los pasos a continuación:
->Encuentre la suma de los números que son divisibles por X hasta N. Denótela como S1.
->Encuentra la suma de los números que son divisibles por Y hasta N. Denota por S2.
->Encuentra la suma de los números que son divisibles tanto por X como por Y (X*Y) hasta N. Denota por S3.
->La respuesta final será S1 + S2 – S3 .
Para encontrar la suma, podemos usar la fórmula general de AP que es:
Sn = (n/2) * {2*a + (n-1)*d}
Para S1 : Los números totales que serán divisibles por X hasta N serán N/X y la suma será:
Hence, S1 = ((N/X)/2) * (2 * X + (N/X - 1) * X)
Para S2 : Los números totales que serán divisibles por Y hasta N serán N/Y y la suma será:
Hence, S2 = ((N/Y)/2) * (2 * Y + (N/Y - 1) * Y)
Para S3 : los números totales que serán divisibles tanto por X como por Y hasta N serán N/(X*Y) y la suma será:
Hence, S2 = ((N/(X*Y))/2) * (2 * Y + (N/(X*Y) - 1) * (X*Y))
Por tanto, el resultado será:
S = S1 + S2 - S3
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find sum of numbers from
// 1 to N which are divisible by X or Y
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the sum
// of numbers divisible by X or Y
int sum(int N, int X, int Y)
{
int S1, S2, S3;
S1 = ((N / X)) * (2 * X + (N / X - 1) * X) / 2;
S2 = ((N / Y)) * (2 * Y + (N / Y - 1) * Y) / 2;
S3 = ((N / (X * Y))) * (2 * (X * Y)
+ (N / (X * Y) - 1) * (X * Y))/ 2;
return S1 + S2 - S3;
}
// Driver code
int main()
{
int N = 14;
int X = 3, Y = 5;
cout << sum(N, X, Y);
return 0;
}
Java
// Java program to find sum of numbers from
// 1 to N which are divisible by X or Y
public class GFG{
// Function to calculate the sum
// of numbers divisible by X or Y
static int sum(int N, int X, int Y)
{
int S1, S2, S3;
S1 = ((N / X)) * (2 * X + (N / X - 1) * X) / 2;
S2 = ((N / Y)) * (2 * Y + (N / Y - 1) * Y) / 2;
S3 = ((N / (X * Y))) * (2 * (X * Y)
+ (N / (X * Y) - 1) * (X * Y))/ 2;
return S1 + S2 - S3;
}
// Driver code
public static void main(String []args)
{
int N = 14;
int X = 3, Y = 5;
System.out.println(sum(N, X, Y));
}
// This code is contributed by Ryuga
}
Python3
# Python 3 program to find sum of numbers from # 1 to N which are divisible by X or Y from math import ceil, floor # Function to calculate the sum # of numbers divisible by X or Y def sum(N, X, Y): S1 = floor(floor(N / X) * floor(2 * X + floor(N / X - 1) * X) / 2) S2 = floor(floor(N / Y)) * floor(2 * Y + floor(N / Y - 1) * Y) / 2 S3 = floor(floor(N / (X * Y))) * floor (2 * (X * Y) + floor(N / (X * Y) - 1) * (X * Y))/ 2 return S1 + S2 - S3 # Driver code if __name__ == '__main__': N = 14 X = 3 Y = 5 print(int(sum(N, X, Y))) # This code is contributed by # Surendra_Gangwar
C#
// C# program to find sum of numbers from
// 1 to N which are divisible by X or Y
using System;
public class GFG{
// Function to calculate the sum
// of numbers divisible by X or Y
static int sum(int N, int X, int Y)
{
int S1, S2, S3;
S1 = ((N / X)) * (2 * X + (N / X - 1) * X) / 2;
S2 = ((N / Y)) * (2 * Y + (N / Y - 1) * Y) / 2;
S3 = ((N / (X * Y))) * (2 * (X * Y)
+ (N / (X * Y) - 1) * (X * Y))/ 2;
return S1 + S2 - S3;
}
// Driver code
public static void Main()
{
int N = 14;
int X = 3, Y = 5;
Console.Write(sum(N, X, Y));
}
}
PHP
<?php
// PHP program to find sum of numbers from
// 1 to N which are divisible by X or Y
// Function to calculate the sum
// of numbers divisible by X or Y
function sum($N, $X, $Y)
{
$S1; $S2; $S3;
$S1 = floor(((int)$N / $X)) * (2 * $X + (int)((int)$N / $X - 1) * $X) / 2;
$S2 = floor(((int)$N / $Y)) * (2 * $Y + (int)((int)$N / $Y - 1) * $Y) / 2;
$S3 = floor(((int)$N / ($X * $Y))) * (2 * ($X * $Y)
+ ((int)$N / ($X * $Y) - 1) * (int)($X * $Y))/ 2;
return ceil($S1 + ($S2 - $S3));
}
// Driver code
$N = 14;
$X = 3;
$Y = 5;
echo sum($N, $X, $Y);
#This code is contributed by ajit.
?>
Javascript
<script>
// javascript program to find sum of numbers from
// 1 to N which are divisible by X or Y
// Function to calculate the sum
// of numbers divisible by X or Y
function sum(N , X , Y)
{
var S1, S2, S3;
S1 = (parseInt(N / X)) * (2 * X + parseInt(N / X - 1) * X) / 2;
S2 = (parseInt(N / Y)) * (2 * Y + parseInt(N / Y - 1) * Y) / 2;
S3 = (parseInt(N / (X * Y))) * (2 * (X * Y)
+ parseInt(N / (X * Y) - 1) * (X * Y))/ 2;
return S1 + S2 - S3;
}
// Driver code
var N = 14;
var X = 3, Y = 5;
document.write(sum(N, X, Y));
// This code is contributed by Princi Singh
</script>
C
// C program to find sum of numbers from
// 1 to N which are divisible by X or Y
#include <stdio.h>
// Function to calculate the sum
// of numbers divisible by X or Y
int sum(int N, int X, int Y)
{
int S1, S2, S3;
S1 = ((N / X)) * (2 * X + (N / X - 1) * X) / 2;
S2 = ((N / Y)) * (2 * Y + (N / Y - 1) * Y) / 2;
S3 = ((N / (X * Y))) * (2 * (X * Y) + (N / (X * Y) - 1) * (X * Y))/ 2;
return S1 + S2 - S3;
}
// Driver code
int main()
{
int N = 14;
int X = 3, Y = 5;
printf("%d ",sum(N, X, Y));
return 0;
}
45
Complejidad de tiempo : O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por gfg_sal_gfg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA