- deadjb
- Aug 11, 2002
-
|
DIW posted:
Assuming you got the equilibrium index one, as that's the one that popped up for me.
Here's a brute force approach in Python. There's probably a better solution though:
code:def equi ( A ):
# write your code here
for i in range(len(A)):
lower = sum(A[:i])
upper = sum(A[i+1:])
if (upper == lower):
return i
return -1
At the risk of Stairway to Heaven-ing this, here's the solution I came up with:
code:int equi ( const vector<int> &A ) {
if (A.size() == 0)
return -1;
vector< pair<long long int, long long int> > sums(A.size());
for (int i = 0; i < A.size(); ++i)
{
int j = A.size()-1-i;
sums[i].first = A[i];
sums[j].second = A[j];
if (i > 0)
sums[i].first += sums[i-1].first;
if (j < A.size()-1)
sums[j].second += sums[j+1].second;
}
for (int i = 0; i < A.size(); ++i)
{
if (sums[i].first == sums[i].second)
return i;
}
if (sums[A.size()-1].second - A[A.size()-1] == 0)
return A.size()-1;
return -1;
}
Yeah, it's ugly, but it works. Sort of embarrassing, since it actually took me a few tries through. I swear it's just because I wasn't used to the interface!
|
#
¿
Feb 15, 2011 13:16
|
|
- Adbot
-
ADBOT LOVES YOU
|
|
#
¿
May 2, 2024 14:46
|
|