Sum of the multiples of two numbers below N
Given three integer A, B and N. The task is to find the sum of all the elements below N which are multiples of either A or B.
Examples:
Input: N = 10, A = 3, B = 5
Output: 23
3, 5, 6 and 9 are the only numbers below 10 which are multiples of either 3 or 5Input: N = 50, A = 8, B = 15
Output: 258
Naive approach:
- Initialise a variable sum = 0.
- Loop from 0 to n for each i check whether i % A = 0 or i % B = 0.
- If the above condition is satisfied, update sum = sum + i.
- Finally return the sum.
Below is the implementation of the above approach:
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> |
23
Time Complexity: O(N), since the loop runs from 0 to (n – 1).
Auxiliary Space: O(1), since no extra space has been taken.
Efficient approach:
For better understanding of an efficient approach let us start from the scratch-
We have the numbers = 1, 2, 3, 4, ………. , N-1 , N
All the numbers divisible by A = A, 2A, 3A, ………….. ?N/A?*A
Let us call this , sum1 =A + 2A + 3A+ …………..+ ?N/A?*A
sum1 = A(1 + 2 + 3+ …………..+ ?N/A? )
sum1 = A* ?N/A? * ( ?N/A? + 1 )/2
Where ? ? is floor (or Least Integer) function .
and sum of n natural numbers formulae n*(n+1)/2 is used.
Similarly sum of numbers divisible by B –
sum2 =B* ?N/B? *( ?N/B? + 1 )/2
So total sum = sum1 + sum2 but there may be some numbers that will be common in both,
For example let N=10, A=2, B=3
Then sum1 = 2+4+6+8+10+12+14+16+18+20
sum2 = 3+6+9+12+15+18
We can clearly see numbers 6, 12, 18 are repeated and all other numbers are multiple of 6 that is the LCM of A and B
Let lcm = LCM of A and B
sum3 =lcm* ?N/lcm? * ( ?N/lcm? + 1 )/2
At last we can calculate the sum by using
sum = sum1 + sum2 – sum3
we can calculate the LCM by using
lcm = (A*B)/gcd
where gcd = GCD of A and B
Below is the implementation of the above approach:
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> |
23
Time Complexity: O(log(N))
Auxiliary Space: O(1)
Contact Us