## Thursday, February 2, 2017

### Divide array into two sub-arrays such that their averages are equal - GeeksforGeeks

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;`
`}`

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;`
`}`
Read full article from Divide array into two sub-arrays such that their averages are equal - GeeksforGeeks