Question

Improve the algorithm by using two for loops instead of three, and analyze the running time of your improved algorithm asymptotically. Show the modified code.

Algorithm FactorSum(A, n)

Input: Array A of n real numbers.

S ← 0

for i ← 0 to n - 1

   for j ← i to n - 1

      P ← 1

      for k ← i to j

         P ← P x A[k]

S ← S + P

return S

Answer 1

Algorithm:

1. First of all, make an array having cumulative multiplication of elements.
2. Cumulative multiplication at any particular index is just the multiplication of all numbers from starting index to that index.
3. Use the two outer loops as it is.
4. For the third loop, we can simply replace it with

   int p;
   if(i!=0)
      p = cumulative_multiplication[j]/cumulative_multiplication[i-1];
   else
      p = cumulative_multiplication[j];

• Below I have used a runnable code to explain you the algorithm:
• You can also test them by running the program with both the algorithms. If the answer from both the algorithms are same, it means we have successfully reduced one loop.

Old Program ( 3 loops ):

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int s = 0;
    int n = 8;
    int A[n] = {1,2,4,5,45,6,78,9};  // Input array A of size n

    // 1st loop
    for(int i=0;i<=n-1;i++)
    {
        // 2nd Loop
        for(int j=i;j<=n-1;j++)
        {
            // 3rd Loop
            int p = 1;
            for(int k=i;k<=j;k++)
            {
                p = p * A[k];
            }
            s = s + p;
        }

    }

     // Finally printing the value of s
    cout << "With 3-loops\n" << endl;
    cout << "Value of s: " << s << endl;
    return 0;
}

Output:

New Program ( 2 loops ):

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int s = 0;
    int n = 8;
    int A[n] = {1,2,4,5,45,6,78,9};  // Input array A of size n

    long int cumulative_multiplication[n]; // Declaring an array to store cumulative multiplication

    // Finding the cumulative multiplication
    cumulative_multiplication[0] = A[0];
    for(int i=1;i<=n-1;i++)
    {
        cumulative_multiplication[i] = A[i] * cumulative_multiplication[i-1];
    }
    // 1st loop
    for(int i=0;i<=n-1;i++)
    {
        // Second loop
        for(int j=i;j<=n-1;j++)
        {

            // Replacing thirst loop with cumulative multiplication
            int p;
            if(i!=0)
                p = cumulative_multiplication[j]/cumulative_multiplication[i-1];
            else
                p = cumulative_multiplication[j];

            s = s + p;
        }

    }

    // Finally printing the value of s
    cout << "With 2-loops\n" << endl;
    cout << "Value of s: " << s << endl;
    return 0;
}

Output:

Please let me know in the comments in case of any confusion. Also, please UPVOTE if you like.