Given an array with n elements, task is to calculate the difference between the sum of those elements occurring at odd indexes and those at even indexes.
Note : For the above problem first we have to check for the bigger sum and from that subtract the smaller sum, either it is of even index or odd index.
Examples:
Input : a[5]={4,3,2,7,8} Output : 4 Input : a[7]={1,1,1,2,2,2,2} Output : 1
Naive Approach:
Simple solution is that while traversing array store the sum of even index elements in one array and odd index elements in another array.
Then calculate the sum of both the arrays and after that subtract the smaller sum from the bigger one.
But here Space complexity is more, as we are using two extra arrays.
So, space complexity will be O(n).
Efficient Approach:
Efficient solution is that store the sum of even index elements in a variable when the index is even and updating onward.
Similarly for the odd index elements and then calculate the higher sum from the lower one.
In this method there is no more space is used, hence space complexity will be O(1).
Below is C++ code implementation:
// C++ implementation of program #include <iostream> #include <algorithm> using namespace std; // Function definition for calculating values int cal(int a[], int n) { int i, even_sum = 0, odd_sum = 0, d; for (i = 0; i < n; i++) { // Check for even case and calculating sum if (i % 2 == 0) even_sum += a[i]; // Check for odd cases else odd_sum += a[i]; } // Check for bigger cases if even index sum is greater if (even_sum > odd_sum) { d = even_sum - odd_sum; } // If odd index sum is greater else d = odd_sum - even_sum; // Returning result return d; } // Driver program int main() { int a[5] = {4, 3, 2, 7, 8}; int diff = 0; int n = 5; // Function call for calculating difference diff = cal(a, n); // Displaying result cout << diff << "\n"; return 0; }
Output:
4