Write a function:
def solution(A)
that, given a zero-indexed array A consisting of N integers, returns any of its equilibrium indices. The function should return −1 if no equilibrium index exists.
For example, given array A shown above, the function may return 1, 3 or 7, as explained above.
Assume that:
N is an integer within the range [0..100,000];
each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.
Time taken to get uptill V 6 - about 6 hours
In [ ]:
Ax = [-1, 3, -4, 5, 1, -6, 2, 1]
V- 1 - used numpy to sum soon realized numpy does not work on codality. I have usually required more time working on solutions when solving something espically with a new technique.
In [4]:
def solution_1(A):
addition_list = list()
list_index = 1
addition_list.append(A[0])
try:
if len(A) >= 0 and len(A) <= 100000:
for i, int_in_arr in enumerate(A):
# print i, " ", int_in_arr
if int_in_arr >= -2 and int_in_arr <= 647 and type(int_in_arr) is int:
if i == 0: continue
addition_list.append(int_in_arr + addition_list[list_index - 1])
print "i: ", i, "\n"
#print A[0:i], "\n"
# print numpy.sum(A[0:i])
#print A[i + 1:], "\n"
# print addition_list
list_index += 1
else:
raise ValueError("one of the array element: integer out of range", int_in_arr)
else:
raise ValueError("array indices out of range ", len(A))
print A
print "\n", addition_list
last_list_index = i
list_index = 1
while list_index != last_list_index:
print addition_list[last_list_index]
if A[list_index-1] == (addition_list[last_list_index] - addition_list[list_index]):
return list_index
except (ValueError, RuntimeError) as err:
print err.args
In [5]:
test = solution_1(Ax)
Solution 2
In [10]:
def solution_2(A):
addition_list = list()
list_index = 1
addition_list.append(A[0])
try:
if len(A) >= 0 and len(A) <= 100000:
for i, int_in_arr in enumerate(A):
# print i, " ", int_in_arr
if int_in_arr >= -2 and int_in_arr <= 647 and type(int_in_arr) is int:
if i == 0: continue
addition_list.append(int_in_arr + addition_list[list_index - 1])
#print "i: ", i, "\n"
#print A[0:i], "\n"
# print math.sum(A[0:i])
#print A[i + 1:], "\n"
# print addition_list
list_index += 1
else:
raise ValueError("one of the array element: integer out of range", int_in_arr)
else:
raise ValueError("array indices out of range ", len(A))
#print A
#print "\n", addition_list
last_list_index = i
list_index = 1
while list_index != last_list_index:
print addition_list[last_list_index]
if A[list_index-1] == (addition_list[last_list_index] - addition_list[list_index]):
return list_index
except (ValueError, RuntimeError) as err:
return err
In [11]:
print solution_2(Ax)
Solution 3
In [16]:
def solution_3(A):
addition_list = list()
list_index = 0
addition_list.append(A[0])
try:
if len(A) >= 0 and len(A) <= 100000:
for i, int_in_arr in enumerate(A):
if type(int_in_arr) is int:
if i == 0: continue
if sum(A[:i]) == (sum(A[:]) - sum(A[:i+1])):
return i
else:
raise ValueError("one of the array element: integer out of range", int_in_arr)
else:
raise ValueError("array indices out of range ", len(A))
return -1
except (ValueError, RuntimeError) as err:
return err
In [17]:
print solution_3(Ax)
solution 4
In [20]:
def solution_4(A):
addition_list = list()
list_index = 0
addition_list.append(A[0])
try:
if 0 == sum(A[1:]):
return 0
elif len(A) == abs(sum(A[:])):
if len(A) % 2:
return len(A)/2
else:
return -1
elif len(A) >= 0 and len(A) <= 100000:
for i in xrange(len(A)):
#if type(int_in_arr) is int:
if i == 0: continue
if sum(A[:i]) == (sum(A[:]) - sum(A[:i+1])):
return i
else:
raise ValueError("one of the array element: integer out of range", int_in_arr)
else:
raise ValueError("array indices out of range ", len(A))
return -1
except (ValueError, RuntimeError) as err:
return err
In [21]:
print solution_4(Ax)
Solution 5
In [25]:
def solution_5(A):
try:
if 0 == sum(A[1:]):
return 0
if len(A) == abs(sum(A[:])):
if len(A) % 2:
return len(A)/2
else:
return -1
elif len(A) >= 0 and len(A) <= 100000:
left_sum = A[0]
right_sum = sum(A[1:])
#print "left_sum: " , left_sum
#print "right sum: ", right_sum, "\n"
for i,val in enumerate(A):
#if type(int_in_arr) is int:
if i == 0: continue
#print A
#print "i: ", i
#print "val: ", val
#print "left sum: ", left_sum
#print "right sum: ", right_sum
#print "\n\n"
right_sum -= val
if left_sum == right_sum:
#print "found match"
return i
left_sum += val
#else:
#raise ValueError("one of the array element: integer out of range", int_in_arr)
else:
return -1
except (ValueError, RuntimeError) as err:
return err
In [26]:
print solution_5(Ax)
Solution 6 - reduced asympottic time complexity by increasing space complexity. O^n
In [29]:
def solution_6(A):
left_sum = 0
right_sum = sum(A[1:])
len_arr = len(A)
try:
if len_arr <= 1:
if len_arr == 1:
return 0
else:
return -1
if left_sum == right_sum:
return 0
#if sum(A[:-1]) == 0:
#return len_arr-1
if len(A) == abs(sum(A[:])):
if len(A) % 2:
return len(A)/2
else:
return -1
if len(A) >= 0 and len(A) <= 100000:
for i,val in enumerate(A):
if i == 0: continue
right_sum -= val
left_sum += A[i-1]
if left_sum == right_sum:
return i
if i >= len_arr:
return -1
else:
return -1
except (ValueError, RuntimeError) as err:
return err
In [30]:
print solution_6(Ax)
Version 7 - Improving Time Complexity - O^n
In [45]:
def solution_7(A):
left_sum = 0
right_sum = sum(A[1:])
len_arr = len(A)
try:
if len_arr <= 1:
if len_arr == 1:
return 0
else:
return -1
if left_sum == right_sum:
return 0
if sum(A[:-1]) == 0:
return len_arr-1
if len(A) == abs(sum(A[:])):
if len(A) % 2:
return len(A)/2
else:
return -1
if len(A) >= 0 and len(A) <= 100000:
left_sum = A[0]
for i,val in enumerate(A[1:]):
right_sum -= val
#left_sum += val
if left_sum == right_sum:
return i+1
left_sum +=val
if i >= len_arr:
return -1
else:
return -1
except (ValueError, RuntimeError) as err:
return err
In [46]:
print solution_7(Ax)
In [ ]:
print "The end"
In [ ]: