HackerRank, Sherlock and Array

Question

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")

Answer 1

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]

Answer 2

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.

Answer 3

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.