Find equilibrium index of the array

Posted in

Find equilibrium index of the array

Vinay Khatri
Last updated on September 21, 2022

    Problem

    Calculate the equilibrium index of an array, given the array of integer numbers. 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 of the index. 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 index i let's say. The sum of 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 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:

    Tags:
    arrary

    Leave a Comment on this Post

    0 Comments