1
\$\begingroup\$

Given an array, find if there is an index where left sum equals to right sum.

My idea is calculate sum, and scan again to see if there is an index for which left_sum equals to total_value - left_sum. My code needs to scan the array twice. I'm wondering if there are any solutions which only need to scan the array once.

import random
def find_index(nums):
    total_value = sum(nums)
    left_sum = 0
    for i,v in enumerate(nums):
        left_sum += v
        if total_value - left_sum == left_sum:
            return i
    return -1

if __name__ == "__main__":
    nums = []
    for i in range(10):
        nums.append(random.randint(0,5))
    print nums
    print find_index(nums)
\$\endgroup\$
  • 2
    \$\begingroup\$ I don't think such a solution exists for one pass. From here: "The trick, is to calculate the sum of all values then do add/subtract until they match..." \$\endgroup\$ – Dair Apr 22 '17 at 1:57
  • 2
    \$\begingroup\$ However, this answer shows that the algorithm can be short circuited if the only positive numbers are considered. \$\endgroup\$ – Dair Apr 22 '17 at 1:59
  • \$\begingroup\$ @Dair, thanks and vote up. I read rolfl's code in the post you referred, but I do not see any advantages of his code comparing to mine. Why do you think his code might be faster than mine? \$\endgroup\$ – Lin Ma Apr 22 '17 at 4:24
1
\$\begingroup\$

Two minor improvments are possible:
1- splitting an array by the sum of the elements only makes sense if the elements are integers. Two equal sums of elements require the total sum over all elements to be even. Check this to shortcut the search.
2- if all elements are positive we can further shortcut the search (see comment).
On my notebook this cuts the runtime to ~ 1/3 for short arrays (len=200) and ~2/3 for long arrays (len=20k).

def find_index2(nums):
    total = sum(nums)
    if total%2 != 0:    # this shortcut only if integer array
        return False, -1
    total /= 2
    L = 0
    for i, v in enumerate(nums):
        L += v
        if L == total:
            return True, i
        if L > total:  # this shortcut only if only positive values in array
            break
    return False, i

edit:
Observing that sum() is faster than elementwise summation I changed the algorithm a bit. Now the majority (here: 50%) of the elements are summed up in one call to sum() and then the exact target value is searched for step by step. Also, I have incorporated @kyrill's comments to remove the restriction for integer values. Still, the assumed property of only positive values is used (see code comments).
Execution time is down to approximately 20% vs. OP's code:

def find_index8(nums):
    total = sum(nums) / 2.
    n = int(len(nums) * .5)  # arbitrary, well-guessed testing index
    S = sum(nums[:n])
    if S == total:
        return True, n-1
    elif S < total:                 # add elementwise
        for i, v in enumerate(nums[n:], n):
            S += v
            if S >= total:    # '>' shortcut only if only positive values in array
                return S==total, i
        return False, -1
    else:                 # subtract elementwise
        for i, v in enumerate(nums[:n][::-1], 2):
            S -= v
            if S <= total:    # '<' shortcut only if only positive values in array
                return S==total, n-i
        return False, -1
\$\endgroup\$
  • 1
    \$\begingroup\$ Why would 1. be true? What about [0.5, 0.5]? BTW you can check if L >= total instead of doing two checks – one for L == total and one for L > total. In most cases, neither is true. So it would be more efficient to do this: if L >= total: return L == total, i. \$\endgroup\$ – kyrill Apr 22 '17 at 20:56
  • \$\begingroup\$ Nice answer user1016274, vote up and mark your reply as answer. \$\endgroup\$ – Lin Ma Apr 24 '17 at 21:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.