Find equilibrium index of the array

Problem

Calculate the equilibrium index of an array of integers.

The equilibrium is the index whereby the total of all numbers strictly on the left side of the index is equal to the sum of all numbers strictly on the right side. If the index is on the left edge of the array, the left value is 0, as no entries exist on the left. This applies to the right array edge as well. Return the leftmost equilibrium index. If no index is available, return -1.

Approach

Assume S as the total sum of the array, and we are at the index, i let's say. The sum of the left elements to the current index is leftsum . The other sum on the right of this index would be only S - nums [ i ] - leftsum if we knew the sum of numbers to the left of the index i .

As such, just to check whether an index is an equilibrium index, just do that: we will keep the proper leftsum value while we iterate over candidate indexes and keep checking the above condition. This takes O(N) time and O(1) auxiliary space.

C++ Programming

#include<bits/stdc++.h>
using namespace std;
int equiIndex(vector<int>& nums) {
        int index=-1;
            int n=nums.size();
            int prefixSum=0;
        int total=0;
        for(auto element:nums)
        {
            total+=element;
        }
            for(int i=0;i<nums.size();i++)
            {
                total-=nums[i];
                if(prefixSum==total)
                {
                    return i;
                }
                  prefixSum+=nums[i];  
               
            }
        return -1;
    }
int main(){
    vector<int>nums{1, 2, 4, 3};
    cout<<equiIndex(nums);
    
}

Output

2

Python Programming

def equiIndex(nums):
    l=len(nums)
    if l==0:
        return -1
    
    total=sum(nums)
    prefixSum=0
    
    for i in range(l):
        total-=nums[i]
        if total==prefixSum:
            return i
        
        prefixSum+=nums[i]
        
    return -1  

nums = [1, 2, 4, 3]
print(equiIndex(nums))

Output

2

C Programming

#include<stdio.h>
int equiIndex(int arr[], int n)
{
    int i, j;
    int prefixSum, total;
 
    /* Check for indexes one by one */
    for (i = 0; i < n; ++i) {      
 
        /* get left sum */
        prefixSum = 0;
        for (j = 0; j < i; j++)
            prefixSum += arr[j];
 
        total = 0;
        for (j = i + 1; j < n; j++)
            total += arr[j];
 
        /* if prefixSum and total are same */
        if (prefixSum == total)
            return i;
    }
 
    return -1;
}
int main(){
    int a[] = {1, 2, 4, 3};
    int n = sizeof(a)/sizeof(a[0]);
    printf("%d", equiIndex(a, n));
}

Output

2

People are also reading:

• Most Asked Pattern Programs in C
• WAP to print given series:1 2 4 8 16 32 64 128
• Programming in C and Java to convert from octal to decimal
• WAP to calculate area of a circle, a rectangle or a triangle
• Print the truth table for XY+Z
• Program to create a loading bar
• Python Program to Make a Simple Calculator
• Convert a given number of days into years, weeks and days
• Find the divisors of a positive Integer
• Display a message on screen