## Microsoft Interview Question

• 0

find the balance index of an array where balanced index i is defined as the one whose left sum is equal to the right sum of the index .
i.e
summation (1 to i-1) = summation (i+1 to length of an array) firdt I gave o(n2) solution , but then before i could give O(n) solution it was time up for me,
O(n) solution will be we have to loop through i = 1 to N and find if ( sum of array - sum of array (1 to i-1 ) = ( sum of array - sum of array (1 to i+1 ) the return i.

Team: bing
Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
15
of 19 vote

here first we traverse the array once to find total sum of array....

then we again start from 0th position and start subtracting value from total sum and go on adding it to leftsum and then compare leftsum and total remaining sum

``````#include<stdio.h>

int equil(int arr[],int size)
{
int i=0,arrsum=0;
int leftsum=0;

for(i=0;i<size;i++)
arrsum+=arr[i];

for(i=0;i<size;i++)
{
arrsum-= arr[i];

if(leftsum == arrsum)
return i;

leftsum+=arr[i];
}

return -1;
}

int main()
{
int arr[] = {-7, 1, 5, 2, -4, 3, 0};
int size = sizeof(arr)/sizeof(arr[0]);
printf("Equilibrium index is : %d",equil(arr,size));

return 0;

}``````

Comment hidden because of low score. Click to expand.
0

pretty cool !!

Comment hidden because of low score. Click to expand.
0

nice

Comment hidden because of low score. Click to expand.
0

Logic is very nice but I think the code has a bug, the

``if(leftsum == arrsum)  return i;``

should come after

``leftsum+=arr[i];``

Comment hidden because of low score. Click to expand.
4
of 4 vote

Hint: Start from both the ends..

``````void find_balance_index() {
int a[]= {1,3,4,6,7,2,5,9,1,11,9,6,5,8,9,1}, i=0, j=0, sum_l=0, sum_r=0;

j = ARRAY_SIZE(a) - 1;
//	if(j%2==0) { printf("-%d---No balance can be found----\n", j); exit(0); }
while(i<j) {
//printf("Indice Values: %d -- %d\n", a[i], a[j]);
if(sum_l < sum_r)
sum_l += a[i++];
else sum_r += a[j--];;
printf("Indices: %d -- %d\t\t", i, j);
printf("SUMs: %d -- %d\n", sum_l, sum_r);

}
if(sum_l == sum_r) printf("Finally The balance is @ %d \n", i);
else printf("-Final---No balance can be found----\n");
}``````

Comment hidden because of low score. Click to expand.
0

i think if array length is even, we can still have balance index.
int[] a = {1,5,5,6} => a[2] is balance index.

Comment hidden because of low score. Click to expand.
0

Does this work if there are negative numbers in the array?

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````int retind(int size)
{
float f=sqrt((size*size-size)/2);
int i=f;
if((f-i)>0)
return -1
else
return i;
}``````

i think this will fix it up..........

Comment hidden because of low score. Click to expand.
0
of 0 vote

edit :
sum of array - sum of array (1 to i-1 ) = ( sum of array - sum of array (i+1 to length of array ) then return i.

Comment hidden because of low score. Click to expand.
0

i have posted a solution .,,,,,,,hope its the best

Comment hidden because of low score. Click to expand.
0
of 0 vote

Is the array sorted?
If it is sorted than take one index i=0 and other index j=n-1;

``````int get_balance_index(int a[n])
{
sum_l=a[i]; sum_r=a[j];
while(1){
if(i>=j )
{
if(sum_l==sum_r)
return i;
else
return -1;
}
if( i+1<j &&sum_l<sum_r)
sum_l+=a[++i];
else if(i< j-1 && sum_l>sum_r)
sum_r+=a[--j];
}``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

If it is not sorted traverse 2 times

``````int get_index_point(int a[n])
{
int sum=0;
//calculate sum
for(int i=0;i<n-1;i++)
sum+=a[i];

//calculate sum/2
int sum_half=0;
for(int i=0; sum_half<sum/2; i++)
sum_half+=a[i];
//Sum(a[0..i-1]) = Sum(a[i..n-1])
if(sum_half-a[i]==sum/2)
return i-1;
else
return -1;
}``````

Comment hidden because of low score. Click to expand.
0

this will only check if the midpoint is balanced index or not ...

eg
in array [10 4 3 2 5] 1st position is the balanced inxdex since leftsum = rightsum = 10

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here, for every i, you have to compute 2 subarray sums: [0, i-1] and [i+1, N-1]. This can be done by maintaining a sum[] array where sum[i] is the sum of the array from 0 to i (inclusive).

Comment hidden because of low score. Click to expand.
0
of 0 vote

The solution of this problem can be achieved by Divide and Conquer rule.
Let us take above mentioned array = {10,4,3,2,5}

1. Find the middle index of the array,In this case index is (0 + 5)/2 = 2.
2. Calculate the sum of two subarrays (Left subarray starting from 0 to index - 1 and right subarray starting from index + 1 to end) and check the condition.In this case left subarray sum up to 10 + 4 = 14 and right subarray 2 + 5 =7.
3. That means now we need to shift the index from 2nd to left.Now the new index is (0 + 2)/2 = 1
4. Left subarray contains 10 and right subarray sum up to 3+ 2 + 5 = 10.So the index is 1 in this case.

Comment hidden because of low score. Click to expand.
0

Your Algorithm works but the time complexity is O(nlogn).

Recurrence Relation:T(n) = T(n/2) + O(n-1) where
T(n/2) is the time complexity to solve the left/right subarray and
O(n-1) is the complexity to compute the sum for both subarrays

If we solve this we will get O(nlogn)

Comment hidden because of low score. Click to expand.
0
of 0 vote

int compute_index(int arr[],int size)
{
int sum1=0,sum2=0;
int i=0,j=size-1;
for( ;i<10 && j>=0;)
{
if(sum1==sum2 && i==j)
return i;
else if(i==j)
return -1;
else if(sum1>sum2)
sum2 =sum2+arr[j--];
else if(sum2>sum1)
sum1=sum1+ arr[i++];
else if(sum2==sum1)
{
sum1 =sum1+arr[i++];
sum2 =sum2+arr[j--];
}
cout<<i<<" "<<j<<" sum1: "<<sum1<<" sum2: "<<sum2<<endl;
}
}

Comment hidden because of low score. Click to expand.
0

Here last line "cout" is not needed.... i.e. only used to check

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static int GetBalancedIndex(int[] inputArray)
{

Int64 arraySum = 0;
Int64 leftSumt = 0;
for (int i = 0; i < inputArray.Length; i++)
{
Console.Write(inputArray[i] + " , ");
arraySum += inputArray[i];
}
Console.WriteLine();
for (int i = 0; i < inputArray.Length; i++)
{
leftSumt += inputArray[i];
arraySum -= inputArray[i];
if (arraySum == leftSumt)
{
Console.WriteLine("Balanced Index {0} : ", i);
return i;
}

}
return -1;

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a simple question. Why are we making it complicated. "Student" has already given the solution.

Comment hidden because of low score. Click to expand.
0

+1

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include<conio.h>
#include<stdio.h>

int balpoint(int a[],int size);
int main()
{
int arr[]={1,3,4,6,7,2,5,9,1,11,9,6,5,8,9,1};
int size= sizeof(arr)/sizeof(arr[0]);
printf("balanced index=%d",balpoint(arr,size));
getch();
return 0;
}

int balpoint(int a[],int size)
{
int leftsum=0;
int rightsum=0;
int i=0;
leftsum=a[0];
for(i=2;i<size;i++)
rightsum +=a[i];
if(leftsum==rightsum)
return 1;
else
{
for(i=2;i<size-1;i++)
{
leftsum +=a[i-1];
rightsum -=a[i];
if(leftsum==rightsum)
return i;
}
}

return -1;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````//if the array is sorted
//worst case complexity O(n)
static void sortedArrayApproch(int sortedArray[]){
if(null==sortedArray ){
System.out.println("not threr");
System.exit(0);
}
int i=0, j = sortedArray.length-1, leftsum=0, rightsum =0;
int loopcount =0;
System.out.println(sortedArray.length);
while(i<j){
loopcount++;
if(leftsum<rightsum)
leftsum+=sortedArray[i++];
else
rightsum+=sortedArray[j--];
if(((j-i)*sortedArray[j])<Math.abs(rightsum-leftsum)){
System.out.println(loopcount);
System.out.println("cannot be fount");
System.exit(0);
}
}
System.out.println(loopcount);
if(leftsum == rightsum)
System.out.println(i);
else
System.out.println("not there");
}
//if we does not know whether array is sorted
//O(n)
static void  unSortedArrayApproch(int a[]){
if(null==a ){
System.out.println("not threr");
System.exit(0);
}
int i=0, j = a.length-1, leftsum=0, rightsum =0;
while(i<j){
if(leftsum<rightsum)
leftsum+=a[i++];
else
rightsum+=a[j--];
}
if(leftsum == rightsum)
System.out.println(i);
else
System.out.println("not there");
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

int index(int arr[],int size)
{
int leftsum=0, rytsum=0, i=0, j=size-1;
while(i!=j)
{
if(leftsum>rytsum)
{
rytsum+=arr[j];
j--;
}
else
{
leftsum+=arr[i];
i++;
}
if(leftsum==rytsum)
cout<<i;
else
count<<"not poss";

Comment hidden because of low score. Click to expand.
0
of 0 vote

While @student already gave a correct answer, I think there's another simple approach to this problem, it does require O(n) space though (so I wouldn't argue this is better than @student's solution)

The idea is to create an auxiliary array which contains the accumulative sum of the original array, then scan through the auxiliary array for element that is exactly half of the last element

``````int FindEquilibriumSimple(const vector<float >& input) {
int num_elem = input.size();
vector<float> sums(num_elem, 0);
sums[0] = input[0];
for (int i = 1; i < num_elem; ++i) {
sums[i] = sums[i-1] + input[i];
}

float target = sums[num_elem - 1] / 2;
for (int i = 0; i < num_elem - 1; ++i) {
if (sums[i] == target) // better to use abs diff < eps
return i;
}

return -1;
}``````

I have implemented both approach and from the test cases I provided so far they produce the same result, try it out here: ideone.com/bsc0f

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a solution in C#

``````public int FindbalancedIndex(int[] array)
{
int low = 0;
int high = array.Length-1;

int lsum=array[low];//sum of array members starting from left
int rsum=array[high];////sum of array members starting from right

while (low < high-1)
{
if (lsum == rsum) //add to both sums and increment both indices
{
lsum += array[++low];
rsum += array[++high];

}
else if (lsum < rsum)
lsum += array[++low];
else
rsum += array[--high];

}
return (lsum == rsum) ? low : -1;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static int getIndex(int[] array)
{

if(array.length==1)
return 0;

int sum= getSum(array);

int tailSum= sum - array[0];

for(int i=1; i<array.length-1; i++)
{
tailSum-= array[i];

return i;
}

return -1;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void findBalancedIndex(int[] inpArr) {
int i = 0;
int j = inpArr.length-1;
int leftSum = inpArr[i];
int rightSum = inpArr[j];
while(i!=j) {
if(leftSum > rightSum) {
j--;
rightSum += inpArr[j];
} else {
i++;
leftSum += inpArr[i];
}
}
if(leftSum == rightSum) {
System.out.println("Balanced index is " + (i+1));
} else {
System.out.println("Balanced index does not exist");
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Question:
array: 1 1 0 0 0 1 1
we have three equilibrium point in this array. Which one should we return?

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.