Given an array arr[] of positive integers and two integers L and R, the task is to find the sum of all multiples of the array elements in the range [L, R].
Examples:
Input: arr[] = {2, 7, 3, 8}, L = 7, R = 20
Output: 197
Explanation:
In the range 7 to 20:
Sum of multiples of 2: 8 + 10 + 12 + 14 + 16 + 18 + 20 = 98
Sum of multiples of 7: 7 + 14 = 21
Sum of multiples of 3: 9 + 12 + 15 + 18 = 54
Sum of multiples of 8: 8 + 16 = 24
Total sum of all multiples = 98 + 21 + 54 + 24 = 197Input: arr[] = {5, 6, 7, 8, 9}, L = 39, R = 100
Output: 3278
Naive Approach: The naive idea is for each element in the given array arr[] find the multiple of the element in the range [L, R] and print the sum of all the multiples.
Time Complexity: O(N*(L-R))
Auxiliary Space: O(1)
Efficient Approach: To optimize the above naive approach we will use the concept discussed below:
- For any integer X, the number of multiples of X till any integer Y is given by Y/X.
- Let N = Y/X
Then, the sum of all the above multiple is given by X*N*(N-1)/2.
For Example:
For X = 2 and Y = 12
Sum of multiple is:
=> 2 + 4 + 6 + 8 + 10 + 12
=> 2*(1 + 2 + 3 + 4 + 5 + 6)
=> 2*(6*5)/2
=> 20.
Using the above concept the problem can be solved using the below steps:
- Calculate the sum of all multiples of arr[i] up to R using the above-discussed formula.
- Calculate the sum of all multiples of arr[i] up to L – 1 using the above-discussed formula.
- Subtract the above two values in the above steps to get the sum of all multiples between ranges [L, R].
- Repeat the above process for all the elements and print the sum.
Below is the implementation of the above approach:
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 Kint 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 sumint 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 Codeint 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 approachimport java.io.*;class GFG{ // Function to find the sum of // all multiples of N up to Kstatic 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 sumstatic 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 Codepublic 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 codeif __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 approachusing System;class GFG{ // Function to find the sum of // all multiples of N up to Kstatic 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 sumstatic 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 Codepublic 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 Kfunction calcSum(k, n){ // Calculate the sum let value = (k * n * (n + 1)) / 2; // Return the sum return value;}// Function to find the total sumfunction 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> |
Output:
197
Time Complexity: O(N), where N is the number of elements in the given array.
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
