current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 1 down vote favorite

Here is the code I have written for a HackerRank challenge which takes multiple arrays, and attempts to determine if there exists an element in an array such that the sum of the elements on its left is equal to the sum of the elements on its right. If there are no elements to the left/right, then the sum is considered to be zero.

Detailed problem statement:

Input Format

The first line contains \$T\$, the number of test cases. For each test case, the first line contains N , the number of elements in the array \$A\$ . The second line for each test case contains N space-separated integers, denoting the array \$A\$.

Output Format

For each test case print YES if there exists an element in the array, such that the sum of the elements on its left is equal to the sum of the elements on its right; otherwise print NO.

It works fine, but it's definitely not an optimal solution, as it fails two test cases (time outs occur). Could anybody provide any insights on optimising it further?

T = int(input())
N = []
A = []

for i in range(T):
    #N.append(int(input()))
    N = int(input())
    arr = input().strip().split(' ')
    arr = list(map(int, arr))
    A.append(arr)
#print(A)
for i in A:
    count=0
    for j in range(len(i)):
        preSum = sum(i[0:j])
        postSum = sum(i[j+1:len(i)])
        if(preSum == postSum):
            count+=1
    if(count>0):
        print("YES")
    else:
        print("NO")
share|improve this question
2  
Welcome to Code Review! As we all want to make our code more efficient or improve it in one way or another, try to write a title that summarizes what your code does, not what you want to get out of a review. Please see How to get the best value out of Code Review - Asking Questions for guidance on writing good question titles. – Mathias Ettinger Jul 4 '16 at 15:45
    
Thanks for the guidance. New here. Will keep it in mind in the future. – snow Jul 4 '16 at 15:54
    
I don't quite understand what N is for. Is it the length of the array? – Graipher Jul 4 '16 at 16:00
    
@Graipher yes. Quite redundant in python, but that's mandatory in the question specs – snow Jul 4 '16 at 16:02
1  
@snow actually, its better for a question to contain everything by itself. – Pimgd Jul 4 '16 at 17:40
up vote 1 down vote accepted

General comments

You should follow PEP8, the coding standard for python. This means using underscore_names for variables instead of camelCase.

i is a bad generic name, except when iterating explicitly over integers. Maybe use for arr in A.

I would use more descriptive variable names. Instead of A use maybe arrays?

Your input could be more succinct:

for i in range(T):
    N = int(input)
    A.append(map(int, input().split()))

This will store a map object in A, instead of a list. But since that is iterable we won't have any problems.

If the input was in one line with the first element being the length of the array and the rest of the line being the array, it would have been even easier:

for i in range(T):
    N, *arr = map(int, input().split())
    A.append(arr)

This uses a nice feature of python3. N will take the first element of an iterable and arr will take all the (possible) rest. You can even specify variables at the end. Try these cases out to get a feel for it:

a, *b = []            # ValueError: not enough values to unpack (expected at least 1, got 0)
a, *b = [0]           # a = 0, b = []
a, *b = [0,1]         # a = 0, b = [1]
a, *b = [0,1,2]       # a = 0, b = [1,2]
a, *b, c = [0]        # ValueError: not enough values to unpack (expected at least 2, got 1)
a, *b, c = [0,1]      # a = 0, b = [], c = 1
a, *b, c = [0,1,2]    # a = 0, b = [1], c = 2

Performance

Instead of always calculating all sums, you could store the pre_ and post_sum and add/subtract the current element. You should also stop after having found one occurrence.

for array in A:
    found = False
    pre_sum, post_sum = 0, sum(array)
    for element in array:
        post_sum -= element
        if(pre_sum == post_sum):
            found = True
            break
        pre_sum += element
    print("YES" if found else "NO")

I'm not exactly sure, but I think there is a small performance difference between these two, for large arr:

arr = list(map(int, arr))
# and
arr = [int(x) for x in arr]
share|improve this answer
    
Flawed code; you print "NO" for each array – Pimgd Jul 4 '16 at 15:54
    
@Pimgd Sorry, just realized this as well, fixed. – Graipher Jul 4 '16 at 15:55
    
Also I think the reason OP uses A and T and N is because the problem statement uses those variable names, which would make them appropriate because it reflects the domain – Pimgd Jul 4 '16 at 15:57
2  
I like reviewing answers as well =) – Pimgd Jul 4 '16 at 15:59
1  
You can't use N, *arr = ...input()... since the length and the values are on two different lines. – Mathias Ettinger Jul 5 '16 at 6:03
up vote 2 down vote

The flaw in your algorithm is that you're summing for each item in each array. That means you get \$O(n^2)\$ for time complexity.

Sum once, then add to the left side whilst removing from the right side. This will give a time complexity of \$O(2n)\$ (once to sum, another to move each element over from the left to the right side).

Additionally, once you have found 1 case in which both sides match, you can stop looking for that testcase.

share|improve this answer
    
Thanks @Pimgd. I generally have problems deciphering the time complexity of programs after writing them. Could you kindly point me to some learning resources which would make me better at it? – snow Jul 4 '16 at 16:33
    
@snow I don't have any specific resources on hand, so here's a google search result from stackoverflow: stackoverflow.com/questions/487258/… – Pimgd Jul 5 '16 at 7:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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