Problem Statement

Find the mean (average) of an array. The mean of an array is defined as the sum of all elements in the array divided by the total number of elements.

Examples

Example 1:

Input: arr = {1, 2, 3, 4,5}
Output: 3

Explanation: Mean = (1+2+3+4+5)/5 = 15/5 = 3

Theory

To calculate the mean of an array using recursion, we can use the following steps:

• Base Case: If the array has only one element, return that element.
• Recursive Step: Recursively calculate the sum of the array elements until we reach the base case.
• Calculation: After reaching the base case, divide the sum by the total number of elements in the array.

Different Approaches

1️⃣ Approach 1: Using Helper Function

Intuition:

• We create a helper function that calculates the sum of array elements.
• Then, we divide this sum by the total number of elements in this array.

Algorithm:

1. Define a helper function arraySum() to calculate the sum of array elements recursively.
2. In the arraySum() function:
   1. If the array has only one element, return that element.
   2. Otherwise, return the sum of the last element and the sum of the remaining elements.
3. Define a function arrayMean() to calculate the mean of the array using the arraySum() function.
4. In the arrayMean() function, return the sum obtained from arraySum() divided by the total number of elements in the array.

arraySum(arr, 5)
    |
    +-- arr[4] + arraySum(arr, 4)
          |
          +-- arr[3] + arraySum(arr, 3)
                |
                +-- arr[2] + arraySum(arr, 2)
                      |
                      +-- arr[1] + arraySum(arr, 1)
                            |
                            +-- arr[0]

Code Implementation in C++:

#include <iostream>
#include <vector>

using namespace std;

// Recursive function to calculate the sum of the array
double sumArray(vector<int>& arr, int n) {
    // Base case: if there's only one element, return it
    if (n == 1) {
        return arr[0];
    }

    // Recursive case: add the current element to the sum of the rest of the array
    return arr[n - 1] + sumArray(arr, n - 1);
}

// Function to calculate the mean using recursion
double meanArray(vector<int>& arr, int n) {
    // Call the recursive sum function and divide by the total number of elements
    double totalSum = sumArray(arr, n);
    return totalSum / n;
}

int main() {
    vector<int> arr = {1, 2, 3, 4, 5}; // Input array
    int n = arr.size(); // Size of the array

    // Calculate and print the mean
    double mean = meanArray(arr, n);
    cout << "Mean of the array: " << mean << endl;

    return 0;
}

Complexity Analysis:

• Time Complexity:O(n)
• Space Complexity:O(n)(due to recursion stack)

2️⃣ Approach 2: Dividing and Conquering

Intuition:

• Divide the array into two parts.
• Recursively calculate the mean of both parts.
• Combine the means of both parts to find the mean of the whole array.

Algorithm:

1. Define a function arrayMean() to calculate the mean of the array.
2. In the arrayMean() function:
   1. If the array has only one element, return that element.
   2. Otherwise, divide the array into two parts and recursively calculate the mean of both parts.\
   3. Return the combined mean of both parts.

           arrayMean(arr, 0, 4)
           /                 \
arrayMean(arr, 0, 2)     arrayMean(arr, 3, 4)
  /      \                 /       \
arr[0]   arrayMean(arr, 0, 1)   arrayMean(arr, 4, 4)
            /       \
        arr[0]      arr[1]

Code Implementation in C++:

#include <iostream>
using namespace std;

// Function to calculate the mean of an array using recursion
double arrayMean(int arr[], int start, int end) {
    if (start == end)
        return arr[start];
    else {
        int mid = (start + end) / 2;
        double left_mean = arrayMean(arr, start, mid);
        double right_mean = arrayMean(arr, mid + 1, end);
        return ((left_mean * (mid - start + 1)) + (right_mean * (end - mid))) / (end - start + 1);
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    double mean = arrayMean(arr, 0, n - 1);
    cout << "Mean of the array: " << mean << endl;

    return 0;
}

Complexity Analysis:

• Time Complexity: O(n)
• Space Complexity:O(log n)