Equilibrium Index Of An Array In C++

An equilibrium index of a sequence is an index within a sequence such that the total elements at lower indices equals the total number of elements at higher indices.

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

3 is the equilibrium index. A{0}+A{1}+A{2}=A{4}+A{5}+A{6}

7 is not an equilibrium because it is not in range.

In other words, an array's equilibrium index is an index i at which the total of elements with indices less than i equals the sum of elements with indices greater than i. We know that the component at index i is not included in either portion, and it is specified that if more than one equilibrium index exists, you must return the first one. If no equilibrium index is found, it Return -1.

Method 1: Using two loops

In this method, we use two loops in which the outer loop continues through all the elements, while the inner loop determines if the current index selected by the outer loop is an equilibrium index. This solution has a time complexity of O(N^2). The objective of this approach is to find the sum of all events for each index. The outer loop traverses the array of values, and the inner loop determines whether or not it contains an equilibrium index.

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

Example


//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)

Calculate the total sum of the array and initialize the left sum of the array to 0. While traversing the array, subtract the current element from the left sum to obtain the correct sum. At each step, double-check the left and right sums . Return the current index if both of them are equal.

The first goal is to obtain the array's total sum. After that, iterate through the array and update the left sum value. We can acquire the correct sum in the loop by subtracting the items individually. Store the array's prefixed sum. The prefix sum could help maintain track of the sum of every element in the array up to any index. Now, we need to figure out how to keep track of the sum of the values that are to the right of the current index's value.

We can utilize a temporary sum variable that initially maintains the sum of the array's elements. We get the total values to the right if we remove the value at the moment from the index. Now, evaluate the leftsum and rightsum values to determine whether the current index corresponds to the equilibrium index.

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

Example


// 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:

Output


The First equilibrium index of the array is 6

Method 3:

It is quite a simple and easy way. The objective is to multiply the array's prefix sum by two. Once using the array's front end and other from its rear end.

After collecting both prefix sums, execute a loop and see if both prefix sums from one array are identical to the corresponding prefix sums from the other array for at least one index 'i'. If this criterion is satisfied, this point might be considered the equilibrium point.

Filename: Equindex. cpp

Example


// 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:

Output


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

Complexity:

Time complexity: O(N)

Space Complexity: O(N)

Method 1: Using two loops

Method 2: (Tricky and efficient)

Method 3:

Input Required