Array Balance Point Finding

Here is a solution to this problem posted on DZone.com

http://java.dzone.com/articles/thursday-code-puzzler-2

Here is my approach to solving
The algorithm needs 2n extra storage space

  1. Create 2 new arrays – of the same size as the original array
  2. In the 1st one – store the running / cumulative total going from 0 to n-1 for each element of the original array
  3. In the 2nd one – store the running / cumulative total going from n-1 to 0 with the lat element of this array  having the same value as the last element of the original array
  4. Then scan both the arrays created in step 2 and 3 and stop at the point where their content is the same if there is no point at which their content is the same – the original array does not have a balance point

Example
Original Array       -1     -2     5     -3
1st Array            -1    -3  2    -1
2nd Array            -1    0    2    -3

Balance point is index 2 in the original array whose value = 5

This is a linear algorithm O(n)

The Python Code is below for this

 

import sys

def findBalancePoint(lst):
print lst
lstB = []
lstF = []
lstB.append(lst[0])
lstF.append(lst[len(lst)-1])
for i in range(1, len(lst)):
lstB.append(lstB[i-1] + lst[i])
j = 0
for i in range(len(lst)-2,-1, -1):
x = lst[i] + lstF[j]
j = j+1
lstF.insert(j,x)
for i in range(len(lstB) – 1):
if ( lstB[i] == lstF[len(lstB) – 1-i] ):
print “Balance Point : ” +  str(i)
return
print “No perfect Balance Point”
return

lst = [int(sys.argv[i]) for i in range(1,len(sys.argv))]
findBalancePoint(lst)

 

 

 

Advertisements

2 responses to “Array Balance Point Finding

  1. Thank you, I’ve recently been looking for information about this subject for a long time and yours is the greatest I’ve discovered
    so far. But, what concerning the bottom line? Are
    you sure in regards to the supply?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s