From http://blog.codility.com/2011/03/solutions-for-task-equi.html
The task is to solve an equilibrium problem. The equilibrium index of a sequence 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 a sequence A:
A[0]=-7 A[1]=1 A[2]=5 A[3]=2 A[4]=-4 A[5]=3 A[6]=0
i.e.
A = [-7, 1, 5, 2, -4, 3, 0]
3 is an equilibrium index, because:
A[0]+A[1]+A[2]=A[4]+A[5]+A[6]
6 is also an equilibrium index, because:
A[0]+A[1]+A[2]+A[3]+A[4]+A[5]=0
When I try to write a super pythonic answer, i.e.:
def solution(A):
for i in range(len(A)):
if sum(A[:i]) == sum(A[i+1:]):
return i
return -1
I get a worst-case complexity of O(N**2). Why is that so?
How do I get a best case complexity of O(N)?
Does this give me O(N)? Why is that so?
def solution(A):
total = sum(A)
sum_left = 0
for i in range(len(A)):
sum_right = sum - sum_left
if sum_left == sum_right:
return i
return -1
Yes, your solution is O(N) and it's because you iterate through the list only once and each iteration is O(1). Your previous solution also iterated through the list one but it summed all elements inside each iteration which made each iteration O(N) too, resulting in the total complexity of O(N^2).
But I think your solution is wrong - you are not accumulating the sum_left. You have to add A[i] inside the loop.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments