- Practice
- Algorithms
- Search
- Sherlock and Array
- Discussions

# Sherlock and Array

# Sherlock and Array

himadri77 + 44 comments For the test cases which contains a

**single element**, make sure that you print**YES**, otherwise you will fail the Test #6. I think it is a huge mistake of the author, because it is not specified at all!For example for input:

`1`

`1`

`1`

Make sure your answer is:

`YES`

whotf + 2 comments +1, thanks!

sandip414 + 0 comments [deleted]RISINGCODER14 + 0 comments https://www.hackerrank.com/challenges/sherlock-and-array/submissions/code/105519037

putting condition is not necessary.check this out.

sandip414 + 4 comments I wasted hackos before reading your post. :(

KarimIhab + 0 comments +1 Thanks.

sunnypav + 0 comments [deleted]TboneMcScreedle + 0 comments NOOO, NOT THE HAACKOS! :'-(

shrirangpatil191 + 0 comments same here

sthomas32 + 1 comment Won't that cause other tests to fail?

edit: I just tried printing "YES" if input is length 1, it caused all tests to fail. Is there an actual workaround for this?

KarimIhab + 3 comments You need to do this:

if( arrSize ==1){

int c = in.nextInt(); System.out.println("YES");

continue; }where c is the current input from STDN. and you continue so that you can go to the next testcase.

sthomas32 + 1 comment When I print YES if length is 1, then all the other test cases fail because they don't expect that.

KarimIhab + 0 comments What do you mean by, they don't expect that. c=in.nextInt(); lets you continue to the next test case normally. If your code works on all the other test cases normally, then all you have to do is this :

[JavaCode]

`if( arrSize ==1){ //you must add this line int c = in.nextInt(); //currentInput. System.out.println("YES"); continue; //Continue to the next test case. }`

raghuramdr + 0 comments [deleted]sattujaiswal + 0 comments ya its working..but didn't understand

sauravdas90 + 2 comments I checked against a custom input of 1 1 1

the answer comes out as YES. but why it is failing? need help

rvrishav7 + 0 comments because sum is to be tsken from left and right and if no such lements exists then obviously answer should be "no" as sum is not equal to that value from either side..

tushartyagi8750 + 0 comments same problem with me

the_piranha + 0 comments And I wasted 6 months in this . Thank you :) . Finally I can be in peace . +1 :)

Ehouarn + 0 comments True they should rephrase it.

noble_liar + 1 comment [deleted]Ehouarn + 0 comments [deleted]

Genw78 + 1 comment Technically, if you've coded things to the problem statement, you don't even need to consider this special case, although it could technically shortcut the rest of your logic.

lilbyrdie + 2 comments Exactly. Not only that, but a general solution would handle negatives and 0, too (which isn't specified). A single element isn't a special case, in my thinking, but rather than case where the sum of the left and the sum of the right of the single element are equal (0).

*shrug*yooyhung + 1 comment But look at the sample input

2

3

1 2 3

4

1 2 3 3

the result is

NO

YES

if the single element should be YES, the the result should be

YES

YES

NO

YES

YES

right?warrior_of_light + 1 comment If the given input n (here 3 and 4) is equal to 1, then only we have to print yes.

yooyhung + 1 comment Oops i think i misunderstood the test description.

For input

2 -> how many test case will coming

3 -> how many element in the first test case

1 2 3 -> the actual first test case

4 -> how many element in the second test case

1 2 3 4 -> the actual second test caseI thought the 2, 3 and 4 are also test cases :(

But now it's clear to me , thanks #warrior_of_lightwarrior_of_light + 0 comments If n == 1, then definitely answer is YES, for n > 1, you have to check.

nirajakonda + 2 comments // java method which passes 6 test cases, 7th test case fails. what is //the problem? // Complete the balancedSums function below.

`static String balancedSums(List<Integer> arr) { int n = arr.size(); int i = 0; int j = n-1; int left = 0; int right = 0; while ( i < n && j >= 0) { if ( left == right && i == j) { return "YES"; } if ( left > right) { right += arr.get(j); j--; } else { left += arr.get(i); i++; } } return "NO"; }`

nishantmaharishi + 0 comments Before returning "NO", just check if left and right are equal or not, if they are equal return "YES". Then it will pass all the test cases. By the way your code is really good.

Kanahaiya + 0 comments Hi,

Here is the video explanation of my solution with different approach in O(n) time-

any feedback or comment would be highly appreciated.

imanurag + 6 comments Didn't need to do it.

for( int i = 0 ; i < n ; i++)

`{ scanf("%d", &a[i]); rc += a[i]; } for( int i = 0 ; i < n ; i++) { lc += a[i-1]; rc -= a[i]; if(lc == rc) { flag = 1; break; } } if(flag == 1) printf("YES\n"); else printf("NO\n"); }`

Balaji_4 + 3 comments for( int i = 0 ; i < n ; i++)

{`lc += a[i-1]; ... You will get ArrayIndexOutOfBoundsException for i=0`

imanurag + 1 comment [deleted]damas + 1 comment It's pretty obvious you have an ArrayIndexOutOfBoundsException even without trying

imanurag + 1 comment [deleted]damas + 1 comment If it makes you feel better I tried it, and it has array index out of bound exception. Just revisit it and you'll see. And once again it's clear even without trying. You start at i=0 and you are trying to access item at i-1 which is index -1

imanurag + 4 comments [deleted]sunnypav + 0 comments Hi Buddy,

You have an array index out of bounds in u r code at line 24 because of negative index. Also, add a condition that if length is 1 display YES.

for( int i = 0 ; i < n ; i++) { lc += a[i-1];

Cheers. Good Day.

sunnypav + 0 comments Hi Buddy,

You have an array index out of bounds in u r code at line 24 because of negative index. Also, add a condition that if length is 1 display YES.

for( int i = 0 ; i < n ; i++) { lc += a[i-1];

Cheers. Good Day.

[DELETED] + 0 comments [deleted]dgodfrey + 1 comment I can see that the code passes the test cases, but you still have Undefined Behavior for accessing an out of bounds index. a[-1] where a is an array is always undefined behavior. It means anything can happen, including your program appearing to behave correctly.

subratkheti + 1 comment Yes, the code is working without a crash because there is a statment to break the loop if condition match.

slashvar1 + 0 comments No it works probably because the 4 bytes before is accessible and contains 0.

This is a classical undefined behavior case and a case of Â« it works on my computer syndroma Â».

Running compiling/running this code with a different compiler (or on a different arch) may break. Just test it with address sanitizer (-fsanitize=address in gcc/clang) or a similar tool â€¦

RoshithS + 1 comment you will get an exception

erichamion + 1 comment If it's in C/C++, there's no array bounds checking, so there would not be an exception. But as others have said, it's still not correct. It will read from the memory location just before the start of the array. If by chance or due to the specific implementation of the compiler, that memory location happens to hold 0, it will work. On a different system, or with a different compiler, or with different conditions, that memory location may have different contents that change the result.

codeharrier + 0 comments There

*may*not be an exception. It can still seg fault.It's wrong in any case.

shivarajs123 + 0 comments try like this lc += (i==0) ? 0 : a[i-1];

brokenmystery + 0 comments That's some great implementation. used the same logic but my code is way longer than yours

jaelim + 0 comments A minor change as follows will fix your minor problem:

sum_r -= A[0]; for (int j=1; j<n; j++) { sum_l += A[j-1]; sum_r -= A[j]; ... }

Cheers

mithraleo1231 + 1 comment bro could u explain me what the que is plz? what if i have like 1 2 3 4 5 4 3 2 1 ....what answer should i get?

cpuneet981810 + 0 comments u shud get yes as c element whose value is 5, sum of all elements to the left of it (suml) and sum of all elements on right of it(sumr) r equal: suml = sumr 1+2+3+4 = 4+3+2+1

codebloodedsp + 0 comments excellent!

dmitry_boltenko + 2 comments From my point of view everithing pretty obvious imagine that one element it's a middle of array sum on left side = 0 as well as on right side = 0.

dmitry_boltenko + 7 comments `int i = 0; int j = array.length - 1; int sum = 0; while (i != j) { if(sum >= 0) { sum -= array[j]; j--; } else { sum +=array[i]; i++; } } return sum == 0 ? true : false;`

tao_zhang + 0 comments for the last line, you don't need to use ternary operator if all you want is to return a boolean

return sum == 0;

will be suffice

TheEyesightDim + 0 comments Yep, I realized that too! I was looking to see if someone got that and you stated it more succinctly than I would have. It's much faster than the binary search method I originally thought of when I first read the problem.

Siwen + 0 comments Great and Simple Solution!

Starboy65 + 0 comments fantastic algorithm

rajputprakash88 + 0 comments Awesome , Salute..

DishaSurana + 2 comments This fails following: n=4: 0 0 2 0

lkutsarov + 0 comments It passes all test cases, including n=4: 0 0 2 0 !!!! Just copy and paste the whole code, and do not forget to import java.util.Scanner !!!

umangughareja411 + 0 comments You are right This is not also not work for 0 2 0 0

madstuffs + 0 comments it fails for test input 0,0,2,0.

rikkert_menses + 0 comments CHEERS

CynthiaXY + 0 comments Only came to see the comments after realizing that...could have saved 10min...

charvakcpatel007 + 0 comments It's not a mistake, He already said that if there are no element then take right/ left sum = 0. Now for single element there are no element on either side so right and left sum is zero which makes it a "YES"

loveis + 0 comments Not really. I agree with the author. If you remove the single element, then 0 == 0. Thanks for the comment though. was helpfull.

christech81 + 0 comments If the test case contains a single element then there is no left and right sections so the answer should be 'NO'. Good post, I read this too late and feel a little cheated :)

swimcane + 0 comments +1 Thanks

vidushig2 + 1 comment # include

# include

# include

# include

# include

using namespace std;

int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */

int t; cin>>t; for(int i=0;i>n; int a[200005]; for(int k=0;k>a[k]; } int flag=0; for(int k=0;k`} if(flag==1) cout<<"YES"<<"\n"; else cout<<"NO"<<"\n"; } return 0;`

}

This is my code... Failing test case 3 and 4 due to time out.Kindly help.

sagssharma + 1 comment yours code complexity is o(n^2).It can be solved in o(n).

avi_ganguly94 + 0 comments how?

phoenixRises + 0 comments For future readers:

You can keep two variables for left and right sum and set them to zero initially. That way, you don't have to write especially for the test case with 1 element.

meredith + 0 comments I failed at that test case too. Thank you!

kanval87 + 3 comments its really embarrasing. my code passes against the first test and then on submission it passes against 0 , 1 ,2 , 5 while it gets timed out on 3 , 4 and fails on 6. i tried your hack as well but no success. can anybody point out whats wrong i am doing here.

`public class SharlockArraySum {`

`public static void main(String[] args) { Scanner in = new Scanner(System.in); while (true) { if (in.hasNextLine()) { String s = in.nextLine(); if (s.contentEquals("")) { break; } else { String[] strings = s.split(" "); if (strings.length > 1) { int[] numbers = new int[strings.length]; for (int i = 0; i < strings.length; i++) { numbers[i] = Integer.parseInt(strings[i]); } checkIfLeftEqualToRight(numbers); }else if(strings.length == 1){`

// if(Integer.parseInt(strings[0]) == 1){ // System.out.println("YES"); // } } } } else { break; } }

`} private static void checkIfLeftEqualToRight(int[] integers) { int totalIntArrayToLoop = integers.length - 1; int sum = getTotalSum(integers, 0, totalIntArrayToLoop); for (int i = 0; i <= totalIntArrayToLoop; i++) { if (i == 0 || i == totalIntArrayToLoop) { int remained = sum - integers[i]; if (remained == 0) { System.out.println("YES"); return; } } else { int toSubtract = getTotalSum(integers, 0, i - 1); int resultToCheck = sum - (toSubtract * 2) - integers[i ]; if (resultToCheck == 0) { System.out.println("YES"); return; } } } System.out.println("NO"); return; } private static int getTotalSum(int[] num, int start, int stop) { int returnSum = 0; for (int i = start; i <= stop; i++) { returnSum = returnSum + num[i]; } return returnSum; }`

}

phoenixRises + 1 comment I would suggest making the functions inline. You are passing an array to a function in checkIfLeftEqualToRight, which is as it is expensive, and on top of it the maximum array size is 10^5, adding all the more to the running time of the program. Tell me if it works.

kanval87 + 1 comment Hi , Thanks for the reply.

the code has been written in java and sorry for my lack of knowledge but i never heard inline function in java. i tried to look up but didnt find much answere to that. apart from it from my understanding of java , we are passing the refrence of the array object but not the object itself so method is just extension of seprated code. i might be wrong.. in such case i would welcome updated information.

apart from it the logic that i have written it works in two 4 cases while fails in 3. in two timed out is there while in 1 it fails. i am trying to understand what am i doing wrong here logically.

phoenixRises + 1 comment I apologize for not being clear enough. I meant substitute the function call with the function itself. You might have to make slight modifications in the code, which you should be able to do with a little effort. In the else part of your checkifleftequaltoright, you are calling the gettotalsum function, and the call is within the for loop. I think that could be a cause of problem. Try substituting the function call with the function code and see if it works. Have you asked the experts while posting your question?

Tip: Always format your code while you ask a question. The greater the readability of your code, the more likely you get an answer. I have formatted it this time for you. I hope somebody else answers, if my response is not good enough.

`public class SharlockArraySum { public static void main(String[] args) { Scanner in = new Scanner(System.in); while (true) { if (in.hasNextLine()) { String s = in.nextLine(); if (s.contentEquals("")) { break; } else { String[] strings = s.split(" "); if (strings.length > 1) { int[] numbers = new int[strings.length]; for (int i = 0; i < strings.length; i++) { numbers[i] = Integer.parseInt(strings[i]); } checkIfLeftEqualToRight(numbers); } else if(strings.length == 1) { // if(Integer.parseInt(strings[0]) == 1) //{ // System.out.println("YES"); //} } } } else { break; } } } private static void checkIfLeftEqualToRight(int[] integers) { int totalIntArrayToLoop = integers.length - 1; int sum = getTotalSum(integers, 0, totalIntArrayToLoop); for (int i = 0; i <= totalIntArrayToLoop; i++) { if (i == 0 || i == totalIntArrayToLoop) { int remained = sum - integers[i]; if (remained == 0) { System.out.println("YES"); return; } } else { int toSubtract = getTotalSum(integers, 0, i - 1); int resultToCheck = sum - (toSubtract * 2) - integers[i]; if (resultToCheck == 0) { System.out.println("YES"); return; } } } System.out.println("NO"); return; } private static int getTotalSum(int[] num, int start, int stop) { int returnSum = 0; for (int i = start; i <= stop; i++) { returnSum = returnSum + num[i]; } return returnSum; } }`

kanval87 + 1 comment Please accept my thanks for answering to my queries as well as helping me out :)

phoenixRises + 1 comment You're welcome. Is your solution now passing all test cases?

kanval87 + 0 comments unfortunately no , the issue is with logic i think. i am solving other puzzles in the mean while and letting my mind cool down for this logic :).

i_am_malav + 0 comments Here If you see n : 1<= n <= 10 ^ 5 So it is not right way to call getSum method everytime for given array which has lenght of 10 ^ 5. Try not to call getSum method many times as it is too expensive. Seel my code below if it can help you out: import java.io.

*; import java.util.*;public class Solution { int n; int[] nums;

`public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t =sc.nextInt(); Solution[] s = new Solution[t]; for(int i = 0 ; i < t ; i++ ) { s[i] = new Solution(); s[i].n = sc.nextInt(); s[i].nums = new int[s[i].n]; for(int j =0 ; j < s[i].n ;j++) { s[i].nums[j] = sc.nextInt(); } boolean match = false; int totalSum = getSum(0, s[i].n - 1, s[i].nums); int previousSum = 0, leftSum =0, rightSum = 0; for( int k = 0 ; k < s[i].n ; k++ ) { previousSum = previousSum + s[i].nums[k]; leftSum = previousSum - s[i].nums[k]; rightSum = totalSum - leftSum - s[i].nums[k]; if(leftSum == rightSum) { match = true; break; } } if(match) System.out.println("YES"); else System.out.println("NO"); } } public static int getSum(int startIndex, int endIndex, int[] arr) { int sum =0; for(int i = startIndex; i<= endIndex; i++) sum = sum + arr[i]; return sum; }`

}

Anwar_Siddiqui + 0 comments static String solve(int[] a){ int len =a.length; int j=len-1; int i=0, sum1=0, sum2=0; while(i<len && j>=0){ if(sum1==sum2 && ((i-j)==0)){ return "YES"; }else if(sum1<sum2){ sum1+=a[i++]; }else{ sum2+=a[j--]; } } return "NO"; }

warrior_of_light + 0 comments Thanks a lot himadri77 :D

Tanisha23 + 0 comments Thanx a lot..!! Saved my day :)

tomsaju + 2 comments I Don't know how. But without checking for array length, my code passed all tests. Following is what i did-

for(int i=0;i<n;i++){ sumr-=a[i]; if(sumr==suml){ count++; break; } suml+=a[i]; }

ganxperia + 0 comments My logic is similar to yours. But I have declared everything as int. Large number inputs are failing in my case and i am pretty sure that my logic is correct. How can we handle large sums?

garima_kamboj + 0 comments Thanks @Tomsaju :) This approach really helped me passing the testcases #3 and #4 as i was getting timeout earlier.

vinothrocksyou + 1 comment Hey it's mentioned in the problem, if you do not find any element to its left or right. It should be considered as zero.

In this case for 1 left = 0 right = 0

both are same, print Yes

apolo4pena + 0 comments [deleted]

chatterjeeronak + 0 comments I think when he mentioned that in case of no element is present left/right, he did kind of gave a hint about such a scenario.

themast3r + 1 comment This is utter foolishness of the writer, for an array of size there exists no element to the right or left of the found element has hence the entire idea of test case, the only I was failing, is completely absurd.

apolo4pena + 0 comments [deleted]

rahulshetty96 + 0 comments I think that author has not made any mistakes here..It is properly mentioned in the constraints that 1<=N<=100000 and also mentioned that ** If there are no elements to the left/right, then the sum is considered to be zero. ** Considering both the statements,above test case is a valid one.

rahulshetty96 + 0 comments I think that author has not made any mistakes here..It is properly mentioned in the constraints that 1<=N<=100000 and also mentioned that ** If there are no elements to the left/right, then the sum is considered to be zero. ** Considering both the statements,above test case is a valid one.

avi_ganguly94 + 1 comment what if there are only two elements in the array?

rahulshetty96 + 0 comments In that case answer would be NO no matter what the number is.

Example

4 5

if i=0 leftsum = 0 and rightsum = 5 if i=1 leftsum = 4 and rightsum = 0 (also note that Ai>=1)

troyaluis56 + 0 comments If that is correct, the test 0 for:

2

3

1 2 3

4

1 2 3 3

should'nt be this?

YES

YES

NO

YES

YES

the output expected is:

NO

YES

I assumed that is for the row 3 and 5

humoyun_ahmad + 0 comments you saved my day, thanks

psm12se + 0 comments +1, thanks!

I wasted hours thinking why Test #6 is failing before coming to this discussion forum and seeing your comments.

rjack2 + 0 comments Thanks..

ayushjain + 0 comments +1. This case #6 is wrong.

saif01md + 1 comment Have a look at this :) static String solve(int[] a){ // Complete this function int sum=0; int lsum=0; int n=a.length; for(int i=0;i<n;i++){ sum=sum+a[i]; } int rsum=sum; for(int i=0;i<n;i++){ rsum=rsum-a[i]; if(rsum==lsum){ return "YES"; } lsum=lsum+a[i]; } return "NO"; }

Himanshu98 + 0 comments thanks for your support , although we have atmost same approach

arcse007 + 0 comments How to solve the problem "Terminated due to timeout"?

ashok97 + 0 comments No its not mistake by writer, there is writen " If there are no elements to the left/right, then the sum is considered to be zero."

consider

rvrishav7 + 0 comments ** happy coding**

#include <bits/stdc++.h> using namespace std; int main() { int t,n; cin>>t; int i,q; for(q=1;q<=t;q++) { cin>>n; long long int j,s1=0,s2=0,l=0; long long int ar[n]; for(i=0;i<n;i++) {cin>>ar[i]; s2+=ar[i]; } for(i=0;i<n;i++) { if(i>=1) s1+=ar[i-1]; s2=s2-ar[i]; if(s1==s2) {l=1; break;} } if(l==1) cout<<"YES"<<endl; else if(l==0||n==1) cout<<"NO"<<endl; } return 0; }

lkutsarov + 0 comments It is not necessary to make a separate explicit condition that prints "YES" when the size of array is equal to one. It all depends on how a person structures the code. So, this condition could be contained implicitly within the code as a part of one general condition for checking whether the two parts are equal. And when the size of the array is equal to one then the variables of the global condition:

totalSum - intermediateSum - inputArray[i] == intermediateSum

will have values:

intermediateSum=0; totalSum = inputArray[i];

Here is my solution for Java:

public class SherlockAndArray { public static void main(String[] args) { Scanner reader = new Scanner(System.in); int numberOfTestCases = reader.nextInt(); String[] results = new String[numberOfTestCases]; for (int i = 0; i < numberOfTestCases; i++) { int numberOfelements = reader.nextInt(); int[] inputArray = new int[numberOfelements]; int totalSum = 0; for (int j = 0; j < numberOfelements; j++) { inputArray[j] = reader.nextInt(); totalSum += inputArray[j]; } String answer = solve(inputArray, totalSum); results[i] = answer; } for (int i = 0; i < numberOfTestCases; i++) { System.out.println(results[i]); } } public static String solve(int[] inputArray, int totalSum){ String result = "NO"; int intermediateSum = 0; for (int i = 0; i < inputArray.length; i++) { if (totalSum - intermediateSum - inputArray[i] == intermediateSum) { result = "YES"; return result; } intermediateSum += inputArray[i]; } return result; } }

facitoo + 0 comments **easy**... just add all the elements of the array! in a loop as the array elements to a new variable and substract the upcoming elemet from the total! compare the two! if equal print yes else no! passes 1 1 1# 6th test case

madstuffs + 0 comments [deleted]csixteen + 0 comments There is no need to have a separate check for singleton lists.

def balanced_sums(arr): total = sum(arr) so_far = 0 for i in arr: if total - i == 2*so_far: return 'YES' else: so_far += i return 'NO'

Kanahaiya + 0 comments Hi All,

I have uploaded a video tutorial on Sherlock and Array solution.

Please have a look and suggest if you have better apporach to solve this problem.

Regards,

Kanahaiya Gupta

RISINGCODER14 + 0 comments its not necessary that you will necessarily fail.depends on code. mine worked without it

Apprentice_ + 5 comments The way to do it in O(n) time is to take advantage of the fact that the right and left sides will always contain all the elements except for the current one. So when looping left to right, if one sets the right to contain the sum of all the elements in the array save the first (depends on your implementation), and the left to start off as zero, they can go through the entire array adding the previous element to the left and subtracting the current element from the right then comparing. It becomes a matter of a very simple loop that contains two add/subtract operations and the comparison, and it will only loop over the array one time.

Matt_Scandale + 1 comment Thank you, that did it! A lot of these challenges require mathematical trickery/shortcuts. "Brute force" coding won't work for a lot of them. The result is that many of these challenges measure mathematical ability more than they measure coding ability.

RalphD + 0 comments Well, after all this problem is in the Algorithms section. Finding out a way to reduce time complexity is all about skillfulness in algorithmic programming.

Mind you, if it really were only mathematical trickery such as knowing some obscure theorem in number theory, then I would agree with you. But this rather is algorithmic trickery which is to be expected with algorithmic exercises.

KarimIhab + 0 comments Thanks Man.

dkvasnicka + 1 comment Subtracting from

*what*exactly? What can you subtract from if you don't know the rest of the array? O(n) means that you are able to solve this while reading the numbers in. If you read the array first and then work on top of it it's not O(n).Apprentice_ + 3 comments Yeah you would have to read the numbers into the array first, and yeah that could definitely potentially mean going through the entire array twice, or one and a half times, etc. But it should be noted here that this is still considered a linear rate of growth, and thus stated generally to be O(n). The fact that it could potentially be 2n does not matter much in the long run, what's important is that it's linear. That's how big O notation is typically used and it is to give a general idea of the eventual rate of growth.

dkvasnicka + 0 comments I understand and agree... I was just confused by everyone talking about having solved it in a single pass.

dmitry_boltenko + 1 comment From my point of view it is not even O(2n). We should take in count complexity of solving algorithm, not complexity of preparing input data.

codeharrier + 1 comment It's O(2n) because you have to have the sum before you can look for the pivot, and worse case this takes two full traversals of the array, minus the first and last elements, but if the array is very large leaving those two elements out makes little difference to the worst-case time. So in the limit where n goes to infinity and the inputs are stacked against you, it takes 2n steps through the array to find the answer.

And that's only if you combine the summing with the inputting. If you do all the inputting and then do the summing and then do the searching, it's O(3n).

Bad_Jim + 0 comments Big O notation ignores the constant factor. Whether your code goes through the array once, twice or even a hundred times, it is still O(n), as long as the number doesn't increase as n increases.

dmitry_boltenko + 1 comment From my point of view it is not even O(2n). We should take in count complexity of solving algorithm, not complexity of preparing input data.

r1singh + 1 comment so can you please tell me how to reduce it ? i mean the complexity? because i am not able to clear 1 test case.

dmitry_boltenko + 0 comments Do you have trouble with test case that is posted for this task? If so I posted above implementation that passed all tests for this task.

r1singh + 0 comments what about this testcase 1 7 5 1 4 13 1..

karadeniz + 0 comments Thank you very much. I was going for O(n^2) after trying more I reached O(n^2/2) or something. After reading your comment I realized I was still doing lots of unnecessary calculations.

10/10

shubhamgoyal1101 + 3 comments python 3 code, easy to understand :) . It takes linear time

def solve(a): # Complete this function summy=sum(a) l=len(a) lefty=0 for i in range(len(a)): current=a[i] summy-=current if lefty==summy: return 'YES' lefty+=current return 'NO'

martinberoiz + 0 comments loved it

Ajey01 + 0 comments great !!! best solution ..

nicmakaveli + 0 comments I had a similar idea, but yours is way better. Helped me figure out why mine was so slow:

def solve(a): # Complete this function if len(a) == 1: return "YES" for i in range(1, int(len(a)+1/2)): left = sum(a[:i]) right = sum(a[i+1:]) if left == right: return "YES" break else: return "NO"

Instead of computing the sum each time, just subtract. Way more efficient. Thank you for sharing.

emivulpe + 2 comments Python solution. Comments would be appreciated

# Enter your code here. Read input from STDIN. Print output to STDOUT def exists_element(size, arr): sum_left = 0 sum_right = sum(arr) previous = 0 for idx in range(0, size): current = arr[idx] sum_left += previous sum_right -= current if sum_left == sum_right: return "YES" previous = current return "NO" test_cases = int(raw_input()) for i in range(0, test_cases): size = int(raw_input()) arr = map(int, raw_input().split()) print exists_element(size, arr)

liyuekui + 1 comment No need to sum(arr) at all, that would cause another uneccesary O(n), here's my code:

def solve(a, size): # Complete this function difference = 0 left_index = 0 compare_count = size - 1 for i in xrange(size+1): if difference > 0: difference -= a[compare_count + left_index - i] else: difference += a[left_index] left_index += 1 return 'YES' if difference == 0 else 'NO'

reis_vitore + 1 comment Failed Testcase 1!

liyuekui + 0 comments Thanks for feedback, code was updated and it passed all cases.

rjack2 + 0 comments Very nice. This helped me get through my timeouts.

mayankharbola25 + 2 comments My approach in C++

#include<bits/stdc++.h> using namespace std; int main(){ int t; cin>>t; for(int i = 0;i<t;i++){ int n;cin>>n; int arr[n]; for(int j = 0;j<n;j++){ cin>>arr[j]; } int start = 0,end = n-1; int sum1 = 0,sum2= 0; for(int j = 0;j<n;j++){ if(j ==0){ sum1 = sum1 + arr[start]; sum2 = sum2 + arr[end]; } else if(start<end){ if(sum1 < sum2){ ++start; sum1 += arr[start]; } else{ --end; sum2 += arr[end]; } } else{ break; } } (sum1 == sum2)? cout<<"YES"<<endl : cout<<"NO"<<endl; } return 0; }

saurabhsingh8362 + 0 comments Nice chutiya

Kanahaiya + 0 comments Hi,

Here is the video explanation of my solution in O(n) time-

any feedback or comment would be highly appreciated.

madstuffs + 2 comments I have used an implementation which takes care of that test case by itself. Here is a Java implementation which passes all test case in o(n) time.

private static String balancedSums(List<Integer> arr) { int sum = 0; // get sum of all array index. for (int i = 0; i < arr.size(); i++){ sum += arr.get(i); } // initially left sum is zero. int leftSum = 0; for (int i = 0; i < arr.size(); i++) { //if left sum equals right sum print yes. if (leftSum == (sum - leftSum - arr.get(i))) { return "YES"; } leftSum += arr.get(i); } return "NO"; }

Vishgen + 1 comment Working Python code:

`leftsum = 0 rightsum = 0 for x in a[1:n]: rightsum += int(x) if leftsum == rightsum: return("YES") for i in range(1,n): leftsum += int(a[i-1]) rightsum -= int(a[i]) if leftsum == rightsum: return("YES") return("NO")`

detuvoldo + 1 comment where is your a[0]?

saptarshi3112191 + 0 comments def check(a,n): if n == 1: return "YES" l = 1 r = n-2 sum_right = a[n-1] sum_left = a[0] while l < r and r >= l : if sum_left

vijithpp + 1 comment Test case 3 and 4 are timed out for me. My code is in python as bellow. Do some one know what is wrong here?

`for i in range(1,len(a)): if sum(a[:i]) == sum(a[i+1:]): return "YES" else : return "NO"`

zahj94 + 0 comments In python, sum(n) function has O(n) time. Because each loop time, you calculate again "left list" and "rigth list", so I can say that your program has O(n^2) time.

To solve this, you should calculate sum_left and sum_right at 0 position outsite your loop, then each loop time, you to do: sum_left += arr[i-1] sum_right -= arr[i] Then compare sum_left and sum_right. With solution, your program will only take O(n) time

shlomi + 0 comments With my initial solution using recursion failed causing timeout for testcases 3,4. My second solution worked just fine. A bit of advice, no nested loops or recursion is necessary.

Sort 491 Discussions, By:

Please Login in order to post a comment