Equilibrium Index Of An Array In C++

An equilibrium index in a sequence refers to an index where the sum of elements before it is equal to the sum of elements after it.

For example, in a sequence A :

A{0}=-8

A{1}=2

A{2}=5

A{3}=2

A{4}=-6

A{5}=3

A{6}=0

The equilibrium point is located at index 3. It signifies that the sum of elements before index 3 is equal to the sum of elements after index 3 in the array.

7 does not qualify as an equilibrium point due to its position outside of the specified range.

In simpler terms, an equilibrium index of an array is an index denoted as i, where the sum of elements with indices less than i is equal to the sum of elements with indices greater than i. It's important to note that the element at index i is not considered in either sum. Furthermore, if there are multiple equilibrium indices, the first one encountered should be returned. If no equilibrium index is present, the function should output -1.

Method 1: Using two loops

In this technique, we employ a pair of loops where the external loop iterates over all elements, while the internal loop assesses if the current index chosen by the external loop qualifies as an equilibrium index. This strategy operates with a time complexity of O(N^2). The aim of this methodology is to compute the total sum of all elements for each specific index. The external loop navigates through the array elements, and the internal loop evaluates the presence of an equilibrium index at that particular position.

The sequence of steps:

• ✅ Making use of two loops.
• ✅ The outer loop of the code iterates through all of the elements, while the inner loop determines whether the current index selected by the outer loop is an equilibrium index.
• ✅ Make a loop through the array.
• ✅ Find the sum of the components to both sides of the current index for every index.
• ✅ The current index is the state of the equilibrium index if the leftsum and rightsum become equal.
• ✅ If not, return -1 .
• ✅ This solution has an O(n^2) time complexity.

Filename: Equilibrium_index.cpp

//This program to find the equilibrium index of the array
#include <bits/stdc++.h>
using namespace std;

int equilibrium_index(int array[], int num)
{
	int i, j;
	int left_sum, right_sum;

	/* Analyse each index one by one until an equilibrium index has been found */
	for (i = 0; i < num; ++i) 
	{	 

		//finding the left sum of the array
		left_sum = 0; 
		for (j = 0; j < i; j++)
			left_sum += array[j];

		//Finding the right sum of the array
		right_sum = 0; 
		for (j = i + 1; j < num; j++)
			right_sum += array[j];

		//checking whether both sum values are equal or not
		if (left_sum == right_sum)
			return i;
	}

	//if not found, any index
	return -1;
}

// Driver code
int main()
{
	int array[] = { -7, 3, 2, 2, -4, 4, 0 };
	int arr_size = sizeof(array) / sizeof(array[0]);
	cout << equilibrium_index(array, arr_size);
	return 0;
}

Output:

Method 2: (Tricky and efficient)

Compute the cumulative sum of all elements in the array and set the initial left sum to zero. While iterating through the array, deduct the current element from the left sum to determine the accurate sum. Continuously verify the sums on the left and right sides. If they are equal at any point, return the current index.

The initial objective is to calculate the cumulative sum of the array. Following this, proceed to iterate over the array and adjust the sum value on the left side. This can be achieved within the loop by subtracting each element individually. Preserve the cumulative sum of the array. This cumulative sum method aids in tracking the total sum of elements in the array up to a specific index. Next, the challenge is to devise a method to monitor the sum of values located to the right of the current index value.

We can use a temporary sum variable to keep track of the sum of the array elements at the beginning. By subtracting the current index value, we can calculate the total values to the right. Then, we compare the leftsum and rightsum values to identify the equilibrium index for the current position.

Algorithm:

• ✅ Set left_sum to zero.
• ✅ Calculate the whole array sum as the sum
• ✅ Iterate through the array, doing the following for each index: i. Update the total to obtain the correct sum.
• ✅ Update the total to obtain the correct sum.
• ✅ sum = sum - array[i]
• ✅ // total is now an accurate sum If left_sum equals sum, return the current index.
• ✅ // Recalculate the leftsum for the next iteration. leftsum = array[i] + left_sum
• ✅ If left_sum equals sum, return the current index.
• ✅ leftsum = array[i] + leftsum
• ✅ return -1 // If we exit the loop without returning, there will be no equilibrium index.

Filename: EqIndex.cpp

// Program for finding the equilibrium index of the array
#include <bits/stdc++.h>
using namespace std;

int equilibrium_index(int array[], int num) 
{ 
	int sum = 0; // total sum of array initialisation 
	int left_sum = 0; // left sum of array

	// calculating the total sum of the array
	for (int i = 0; i < num; ++i) 
		sum += array[i]; 

	for (int i = 0; i < num; ++i) 
	{ 
		sum -= array[i]; // total is now correct sum for index i

		if (left_sum == sum) 
			return i; 

		left_sum += array[i]; 
	} 

 //if not found, any index
	return -1; 
} 

// main section
int main() 
{ 
	int array[] = { -7, 3, 2, 2, -4, 4, 0 }; 
	int array_size = sizeof(array) / sizeof(array[0]); 
	cout << "The First equilibrium index of the array is " << equilibrium_index(array, array_size); 
	return 0; 
}

Output:

The First equilibrium index of the array is 6

Method 3:

It is a straightforward and uncomplicated method. The goal is to double the prefix sum of the array by two different approaches. One from the beginning of the array and the other from the end of the array.

After obtaining the prefix sums for both arrays, iterate through a loop to compare whether the prefix sums of one array match with the prefix sums of the other array for any given index 'i'. If this condition is met, that particular index could be identified as a potential equilibrium point.

Filename: Equindex. cpp

// Program for finding the equilibrium index of the array
#include <bits/stdc++.h>
using namespace std;

int equilibrium_index(int array[], int num)
{
	if (num == 1)
		return (0);
	int front[num] = { 0 };
	int reverse[num] = { 0 };

	// calculating prefix sum from the initial index of the array
	for (int i = 0; i < num; i++) {
		if (i) {
			front[i] = front[i - 1] + array[i];
		}
		else {
			front[i] = array[i];
		}
	}

	// Taking the prefix sum from the back end of the array
	for (int i = num - 1; i > 0; i--) {
		if (i <= num - 2) {
			reverse[i] = reverse[i + 1] + array[i];
		}
		else {
			reverse[i] = array[i];
		}
	}

	// determining whether the front prefix sum 
	// equals the reverse prefix sum
	for (int i = 0; i < num; i++) {
		if (front[i] == reverse[i]) {
			return i;
		}
	}
	return -1;

	//If you'd like to have all of the equilibrium points
	//construct a vector, insert all the equilibrium points, 
	//and then return the vector.
}

// main section
int main()
{
	int array[] = { -7, 3, 2, 2, -4, 4, 0 };
	int num = sizeof(array) / sizeof(array[0]);
	cout << "The First Point of equilibrium of the array is at index "
		<< equilibrium_index(array, num) << " ";
	return 0;
}

Output:

The First Point of equilibrium of the array is at index 6

Complexity:

Time complexity: O(N)

Space Complexity: O(N)