Equilibrium Point - Equilibrium index of an array

PHOTO EMBED

Mon Feb 07 2022 14:56:33 GMT+0000 (UTC)

Saved by @Uttam #java #gfg #geeksforgeeks #lecture #arrays #prefixsum #equilibriumpoint #equilibriumindex

// Efficient Method : Time Complexity : O(n), Auxilliary space : O(1)

import java.util.*;
import java.io.*;

class GFG 
{ 
    static boolean checkEquilibrium(int arr[], int n)
    {
    	int sum = 0;

    	for(int i = 0; i < n; i++)
    	{
    		sum += arr[i];
    	}

    	int l_sum = 0;

    	for(int i = 0; i < n; i++)
    	{
    		if(l_sum == sum - arr[i])
    			return true;

    		l_sum += arr[i];

    		sum -= arr[i];
    	}

    	return false;
    }

    public static void main(String args[]) 
    { 
       int arr[] = {3, 4, 8, -9, 20, 6}, n = 6;

       System.out.println(checkEquilibrium(arr, n));
    } 
}




// Naive Method : Time Complexity : O(n^2)

    static boolean checkEquilibrium(int arr[], int n)
    {
    	for(int i  = 0; i < n; i++)
    	{
    		int l_sum = 0, r_sum = 0;

    		for(int j = 0; j < i; j++)
    			l_sum += arr[j];

    		for(int j = i + 1; j < n; j++)
    			r_sum += arr[j];

    		if(l_sum == r_sum)
    			return true;
    	}

    	return false;
    }
content_copyCOPY

Equilibrium index of an array is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes. For example, in an array A: Example : Input: A[] = {-7, 1, 5, 2, -4, 3, 0} Output: 3 3 is an equilibrium index, because: A[0] + A[1] + A[2] = A[4] + A[5] + A[6] Input: A[] = {1, 2, 3} Output: -1