Divide array into two sub-arrays such that their averages are equal - GeeksforGeeks
Given an integer array, the task is to divide an integer array into two sub-arrays to make their averages equal if possible.
Read full article from Divide array into two sub-arrays such that their averages are equal - GeeksforGeeks
Given an integer array, the task is to divide an integer array into two sub-arrays to make their averages equal if possible.
An Efficient solution is to find sum of array elements. Initialize leftsum as zero. Run a loop and find leftsum by adding elements of array. For rightsum, we substract leftsum from total sum then we find rightsum and find average of leftsum and rightsum as according to their index.
void findSubarrays(int arr[], int n){ // Find array sum int sum = 0; for (int i=0; i<n; i++) sum += arr[i]; bool found = false; int lsum = 0; for (int i=0; i<n-1; i++) { lsum += arr[i]; int rsum = sum - lsum; // If averages of arr[0...i] and arr[i+1..n-1] // are same. To avoid floating point problems // we compare "lsum*(n-i+1)" and "rsum*(i+1)" // instead of "lsum/(i+1)" and "rsum/(n-i+1)" if (lsum*(n-i-1) == rsum*(i+1)) { printf("From (%d %d) to (%d %d)\n", 0, i, i+1, n-1); found = true; } } // If no subarrays found if (found == false) cout << "Subarrays not found" << endl;}
A Naive Approach is to run two loops and find subarrays whose averages are equal.
void findSubarrays(int arr[], int n){ bool found = false; int lsum = 0; for (int i = 0; i < n-1; i++) { lsum += arr[i]; int rsum = 0; for (int j = i + 1; j < n; j++) rsum += arr[j]; // If averages of arr[0...i] and arr[i+1..n-1] // are same. To avoid floating point problems // we compare "lsum*(n-i+1)" and "rsum*(i+1)" // instead of "lsum/(i+1)" and "rsum/(n-i+1)" if (lsum*(n-i-1) == rsum*(i+1)) { printf("From (%d %d) to (%d %d)\n", 0, i, i+1, n-1); found = true; } } // If no subarrays found if (found == false) cout << "Subarrays not found" << endl;}