Question

print the sum of first 5 multiples using for loop​

Answer 1

Explanation:

The basic idea is to iterate from i = a to i = n, i++ and check whether i % a == 0 or not.If zero then add i to sum(initially sum = 0).Thus we will get the sum.It will take O(n) time.

We can modify the loop as i = a, i <= n, i = i + a to reduce the number of iterations.But it will also take O(m) time if there is m multiples of a.

To get the result in O(1) time we can use the formula of summation of n natural numbers.For the above example,

a = 4 and N = 23, number of multiples of a, m = N/a(integer division). The multiples are 4, 8, 12, 16, 20.

We can write it as 4 X [1, 2, 3, 4, 5]. So we can get the sum of multiples as:

sum = a * (Summation of 1 to m [natural numbers from 1 to m])

sum = 4 * (m*(m+1) / 2)

sum = 4 * (5*6 / 2) = 4 * 15 = 60

// C++ program to find sum of multiples of a number

// up to N efficiently

#include <iostream>

using namespace std;

// Function for calculating sum of multiples of

// a upto N

int calculate_sum(int a, int N)

{

// Number of multiples

int m = N / a;

// sum of first m natural numbers

int sum = m * (m + 1) / 2;

// sum of multiples

int ans = a * sum;

return ans;

}

// Driver code

int main()

{

int a = 7, N = 49;

cout << "Sum of multiples of "

<< a << " up to " << N << " = "

<< calculate_sum(a, N) << endl;

return 0;

}

Hope it's helpful to you