Find Equilibrium Point in Array

Find Equilibrium Point in Array

Medium C++ Arrays 28 views
Explanation Complexity

Problem Statement

Find index where sum of elements before it equals sum after it. This teaches prefix sum concept and optimization.

Logic: Calculate total sum, then track left sum while traversing

Input Format

An integer n (size of array)
Then n integers.

Output Format

Index where sum of elements before it equals sum of elements after it
OR
-1 if no such index exists.

Example

5
1 3 5 2 2

2

Constraints

• n ≥ 1

• Indexing is 0-based

Concept Explanation

At index 2:

• Left sum = 1 + 3 = 4

• Right sum = 2 + 2 = 4
So both sides are equal.

Step-by-Step Explanation

1.Calculate the total sum of all elements in the array.

2.Initialize leftSum = 0.

3.Traverse the array from index 0 to n-1.

4.For current index i:

• Subtract arr[i] from totalSum (now totalSum is right sum).

5.Compare:

• If leftSum == totalSum, then i is the required index.

6.Add arr[i] to leftSum.

7.Continue traversal if not matched.

8.If no index satisfies the condition, print -1.

Concept Explanation

At index 2:

• Left sum = 1 + 3 = 4

• Right sum = 2 + 2 = 4
So both sides are equal.

Step-by-Step Explanation

1.Calculate the total sum of all elements in the array.

2.Initialize leftSum = 0.

3.Traverse the array from index 0 to n-1.

4.For current index i:

• Subtract arr[i] from totalSum (now totalSum is right sum).

5.Compare:

• If leftSum == totalSum, then i is the required index.

6.Add arr[i] to leftSum.

7.Continue traversal if not matched.

8.If no index satisfies the condition, print -1.

Input / Output Format

Input Format
An integer n (size of array)
Then n integers.
Output Format
Index where sum of elements before it equals sum of elements after it
OR
-1 if no such index exists.
Constraints
• n ≥ 1

• Indexing is 0-based

Examples

Input:
5 1 3 5 2 2
Output:
2

Example Solution (Public)

C++ 
void question11_equilibrium_point() {
    int arr[] = {1, 3, 5, 2, 2};
    int size = 5;
    int totalSum = 0, leftSum = 0;
    
    for(int i = 0; i < size; i++) {
        totalSum += arr[i];
    }
    
    for(int i = 0; i < size; i++) {
        totalSum -= arr[i];
        
        if(leftSum == totalSum) {
            cout << "Equilibrium index: " << i << endl;
            return;
        }
        
        leftSum += arr[i];
    }
    
    cout << "No equilibrium point found" << endl;
}

Official Solution Code

void question11_equilibrium_point() {
    int arr[] = {1, 3, 5, 2, 2};
    int size = 5;
    int totalSum = 0, leftSum = 0;
    
    for(int i = 0; i < size; i++) {
        totalSum += arr[i];
    }
    
    for(int i = 0; i < size; i++) {
        totalSum -= arr[i];
        
        if(leftSum == totalSum) {
            cout << "Equilibrium index: " << i << endl;
            return;
        }
        
        leftSum += arr[i];
    }
    
    cout << "No equilibrium point found" << endl;
}
Please login to submit solutions.
Editor
Output

                                        

                                    

                                    

                                        

                                                                                    
Please login to submit solutions.