Please, show all the steps to solve this java and algorithm problem. The balance

Question

Please, show all the steps to solve this java and algorithm problem.

The balance index of an array of integers is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes. The formal definition is: The integer k is an balance index of a sequence of integers S[0]; S[1];...; S[n - 1] if and only if 0 lessthanorequalto k and sigma_i = 0^k - 1 S[i] = sigma_i = k + 1^n - 1 S[i]. Assume the sum of zero elements is equal to zero. For example, in a sequence S: S[0] = -5; S[1] =3; S[2] = 7; S[3] = -8; S[4] = -2; S[5] = 5; S[6] = 2 3 is a balance index, because: S[0] + S[1] + S[2] = S[4] + S[5] + S[6] 6 is also a balance index, because: S[0] + S[1] + S[2] + S[3] + S[4] + S[5] = 0 And the sum of zero elements is zero. Note that the index 7 is not a balance index - because it is not a valid index of sequence S. Implement an efficient function in Java int balIndex(int S[], int n) that, given an array S, returns its balance index (any) or -1 if no balance index exists. What is the running time complexity of your function? Justify.

Explanation / Answer

a) int balIndex(int S[],int n)
{
   int left[] = new int[1000];
   left[0]= 0;
for(int i=1;i<n;i++)
{
   left[i]+=(left[i-1]+S[i-1]);
}
int right[] = new int[1000];
right[n-1]=0;
for(int i=n-2;i>=0;i--)
{
   right[i]+=(right[i+1]+S[i+1]);
}
for(int i=0;i<n;i++)
{
   if(left[i]==right[i])
       return i;
}
         return -1;   
     
}

b) Running complexity of code is : O(n)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.