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)


i:  1 

('one of the array element: integer out of range', -4)

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)


('one of the array element: integer out of range', -4)

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)


1

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)


1

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)


1

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)


1

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)


1

In [ ]:
print "The end"

In [ ]: