4
\$\begingroup\$

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")
\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Mathias Ettinger Jul 4 '16 at 15:45
  • \$\begingroup\$ Thanks for the guidance. New here. Will keep it in mind in the future. \$\endgroup\$ – snow Jul 4 '16 at 15:54
  • \$\begingroup\$ I don't quite understand what N is for. Is it the length of the array? \$\endgroup\$ – Graipher Jul 4 '16 at 16:00
  • \$\begingroup\$ @Graipher yes. Quite redundant in python, but that's mandatory in the question specs \$\endgroup\$ – snow Jul 4 '16 at 16:02
  • 1
    \$\begingroup\$ @snow actually, its better for a question to contain everything by itself. \$\endgroup\$ – Pimgd Jul 4 '16 at 17:40
3
\$\begingroup\$

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]
\$\endgroup\$
  • \$\begingroup\$ Flawed code; you print "NO" for each array \$\endgroup\$ – Pimgd Jul 4 '16 at 15:54
  • \$\begingroup\$ @Pimgd Sorry, just realized this as well, fixed. \$\endgroup\$ – Graipher Jul 4 '16 at 15:55
  • \$\begingroup\$ 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 \$\endgroup\$ – Pimgd Jul 4 '16 at 15:57
  • 2
    \$\begingroup\$ I like reviewing answers as well =) \$\endgroup\$ – Pimgd Jul 4 '16 at 15:59
  • 1
    \$\begingroup\$ You can't use N, *arr = ...input()... since the length and the values are on two different lines. \$\endgroup\$ – Mathias Ettinger Jul 5 '16 at 6:03
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – snow Jul 4 '16 at 16:33
  • \$\begingroup\$ @snow I don't have any specific resources on hand, so here's a google search result from stackoverflow: stackoverflow.com/questions/487258/… \$\endgroup\$ – Pimgd Jul 5 '16 at 7:54
0
\$\begingroup\$

Actually, you are using two nested loop which is having O(n^2) complexity but this can be easily done in O(n) time using one for loop.

Below are steps which will help you to do the same in O(n) time-

You can drive an equation by using a little bit of mathematics.

Assume we have an array which is the random array {3,7,5,10,2,7,4,2} so, in that, that element exists such that the sum of the left side of all the elements is equal to the sum of the right side all the elements.

I am assuming that element is represented by y and it exists in between somewhere. so some of the left side of the element is represented by x as I said the sum of all the elements towards the left side is equal to the sum of all the elements towards the right side of that element. so right side sum also can be represented by x.So by seeing this, we can easily say the sum of all elements presents inside the array should be equal to x + y + x.

x + y + x = sum of all the elements

2 x + y=sum of all the elements

2 x = sum of all the elements - y ---> eq 1

if we have x and y such that this equation holds true. It means, there is one element exist correct because in this equation we have to unknowns x and y. so we have to first get the value of x and y and then will place both the values inside the equation and see whether LHS is equals to RHS or not? LHS equals to RHS it means there is some element exist inside the array where the sum of all the elements towards the left side of the element is equal to the right side of the element. Let’s take one example array.

{3,7,5,10,2,7,4,2}

first, I will calculate the sum of all elements.

sum of all the elements= 3+7+5+10+2+7+4+2 sum of all the elements= 40

replace this in eq 1 then you will get below eq

2x =40 - y --> eq 2

as we are not aware of the y but y that's for sure y will belong to any one of the elements which are present inside the array. so will take one element at a time from the array and replace y with that element like that x also. we will take the x value based on y whatever it comes and replace in this question and see whether LHS equals to RHS or not. if we found any such pair of x and y where LHS equals to RHS. It means, we have that element inside the array which holds this criterion true and we will return YES.

for first iteration- {3,7,5,10,2,7,4,2}

y=3, x=0

just replace both values in eq 2 and you can seed

0 is not equal to 37

now move the pointer ahead try this time

y=7, x=0+3=3

just replace both values in eq 2 and you can seed

6 is not equal to 33

....so do the same until you find that element y which satisfy this condition.

now skipping next iterating with y=5 and trying for y=10 know

if y=10 ,x=3+7+5=15

just replace both values in eq 2 and you can seed

30 is equal to 30. It means this the element(y) which we are looking for and where left sum is equal to the right sum.

Here is the code which passes 100% test case.

static String balancedSums(List<Integer> arr) {
        int x = 0;
        int sum = 0;
        for (int a : arr) {
            sum += a;
        }

        for (int y : arr) {
            if (2 * x == sum - y) {
                return "YES";
            }
            x = x + y;
        }
        return "NO";

    }

Still having doubt you can check out the video tutorial here.

\$\endgroup\$
  • 1
    \$\begingroup\$ This appears nearly identical to your answer from yesterday (which was deleted by the community because it was alternate solution instead of a review) with just a few more paragraphs added to the end... please discuss more about the OPs code. \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Mar 13 at 7:40
  • \$\begingroup\$ Added my analysis on top after deep review. @ Sᴀᴍ Onᴇᴌᴀ \$\endgroup\$ – Kanahaiya Mar 13 at 11:48

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.