Hackerrank's Sherlock and Array
$begingroup$
Challenge can be found here
Problem Statement
Watson gives Sherlock an array A of length N. Then he
asks him to determine 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. If there are no elements to the left/right,
then the sum is considered to be zero. Formally, find an i, such
that, A1+A2...Ai-1 =Ai+1+Ai+2...AN.
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.
Constraints:
$1 le T le 10$
$1 le N le 10^5$
$1 le Ai le 2×10^4$
$1 le i le N$
I'm having timeout issues on 2 of the test cases
I have tried two different approaches. Both is of $O(n^2)$
First was a recursive approach:
public static boolean isEven(int arr, int index, int leftSum, int rightSum) {
int i = index-1;
int j = index+1;
while(i > -1) {
leftSum += arr[i--];
}
while(j < arr.length) {
rightSum += arr[j++];
}
return (leftSum == rightSum) ? true : (index == arr.length-1) ? false : isEven(arr, index+1, 0, 0);
}
Other one was with the use of Navigable
map:
public static boolean isEven(NavigableMap<Integer, Integer> map) {
int left = 0;
int right = 0;
int n = map.size();
while(n-- > 0) {
left = right = 0;
for(Integer i : map.tailMap(n+1).values()) right += i;
for(Integer j : map.headMap(n).values()) left += j;
if (left == right) return true;
}
return false;
}
Here is how I read the input:
public static void main(String args) {
Scanner s = new Scanner(System.in);
final int N = s.nextInt();
for(int i = 0; i < N; i++) {
int NN = s.nextInt();
int arr = new int[NN];
for(int j = 0; j < NN; j++) {
arr[j] = s.nextInt();
}
System.out.println(isEven(arr, 0, 0, 0) ? "YES" : "NO");
}
}
To avoid an $O(n^2)$ solution, I can't check every element in the array, or can I?
java performance algorithm programming-challenge search
$endgroup$
add a comment |
$begingroup$
Challenge can be found here
Problem Statement
Watson gives Sherlock an array A of length N. Then he
asks him to determine 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. If there are no elements to the left/right,
then the sum is considered to be zero. Formally, find an i, such
that, A1+A2...Ai-1 =Ai+1+Ai+2...AN.
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.
Constraints:
$1 le T le 10$
$1 le N le 10^5$
$1 le Ai le 2×10^4$
$1 le i le N$
I'm having timeout issues on 2 of the test cases
I have tried two different approaches. Both is of $O(n^2)$
First was a recursive approach:
public static boolean isEven(int arr, int index, int leftSum, int rightSum) {
int i = index-1;
int j = index+1;
while(i > -1) {
leftSum += arr[i--];
}
while(j < arr.length) {
rightSum += arr[j++];
}
return (leftSum == rightSum) ? true : (index == arr.length-1) ? false : isEven(arr, index+1, 0, 0);
}
Other one was with the use of Navigable
map:
public static boolean isEven(NavigableMap<Integer, Integer> map) {
int left = 0;
int right = 0;
int n = map.size();
while(n-- > 0) {
left = right = 0;
for(Integer i : map.tailMap(n+1).values()) right += i;
for(Integer j : map.headMap(n).values()) left += j;
if (left == right) return true;
}
return false;
}
Here is how I read the input:
public static void main(String args) {
Scanner s = new Scanner(System.in);
final int N = s.nextInt();
for(int i = 0; i < N; i++) {
int NN = s.nextInt();
int arr = new int[NN];
for(int j = 0; j < NN; j++) {
arr[j] = s.nextInt();
}
System.out.println(isEven(arr, 0, 0, 0) ? "YES" : "NO");
}
}
To avoid an $O(n^2)$ solution, I can't check every element in the array, or can I?
java performance algorithm programming-challenge search
$endgroup$
2
$begingroup$
@Vogel612 "Code Review is about improving existing, working code". My code does work. I just need to improve it's speed.
$endgroup$
– Nilzone-
Jun 14 '15 at 21:11
$begingroup$
fuu... sorry I missed the "timeout" in the issues statement, my bad. Are all other test-cases going through cleanly?
$endgroup$
– Vogel612♦
Jun 14 '15 at 21:16
$begingroup$
@Vogel612. Yes. I can provide a screenshot if you'd like.
$endgroup$
– Nilzone-
Jun 14 '15 at 21:17
1
$begingroup$
no need, I trust you, and skimming over the code looks like it should work ;)
$endgroup$
– Vogel612♦
Jun 14 '15 at 21:18
add a comment |
$begingroup$
Challenge can be found here
Problem Statement
Watson gives Sherlock an array A of length N. Then he
asks him to determine 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. If there are no elements to the left/right,
then the sum is considered to be zero. Formally, find an i, such
that, A1+A2...Ai-1 =Ai+1+Ai+2...AN.
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.
Constraints:
$1 le T le 10$
$1 le N le 10^5$
$1 le Ai le 2×10^4$
$1 le i le N$
I'm having timeout issues on 2 of the test cases
I have tried two different approaches. Both is of $O(n^2)$
First was a recursive approach:
public static boolean isEven(int arr, int index, int leftSum, int rightSum) {
int i = index-1;
int j = index+1;
while(i > -1) {
leftSum += arr[i--];
}
while(j < arr.length) {
rightSum += arr[j++];
}
return (leftSum == rightSum) ? true : (index == arr.length-1) ? false : isEven(arr, index+1, 0, 0);
}
Other one was with the use of Navigable
map:
public static boolean isEven(NavigableMap<Integer, Integer> map) {
int left = 0;
int right = 0;
int n = map.size();
while(n-- > 0) {
left = right = 0;
for(Integer i : map.tailMap(n+1).values()) right += i;
for(Integer j : map.headMap(n).values()) left += j;
if (left == right) return true;
}
return false;
}
Here is how I read the input:
public static void main(String args) {
Scanner s = new Scanner(System.in);
final int N = s.nextInt();
for(int i = 0; i < N; i++) {
int NN = s.nextInt();
int arr = new int[NN];
for(int j = 0; j < NN; j++) {
arr[j] = s.nextInt();
}
System.out.println(isEven(arr, 0, 0, 0) ? "YES" : "NO");
}
}
To avoid an $O(n^2)$ solution, I can't check every element in the array, or can I?
java performance algorithm programming-challenge search
$endgroup$
Challenge can be found here
Problem Statement
Watson gives Sherlock an array A of length N. Then he
asks him to determine 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. If there are no elements to the left/right,
then the sum is considered to be zero. Formally, find an i, such
that, A1+A2...Ai-1 =Ai+1+Ai+2...AN.
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.
Constraints:
$1 le T le 10$
$1 le N le 10^5$
$1 le Ai le 2×10^4$
$1 le i le N$
I'm having timeout issues on 2 of the test cases
I have tried two different approaches. Both is of $O(n^2)$
First was a recursive approach:
public static boolean isEven(int arr, int index, int leftSum, int rightSum) {
int i = index-1;
int j = index+1;
while(i > -1) {
leftSum += arr[i--];
}
while(j < arr.length) {
rightSum += arr[j++];
}
return (leftSum == rightSum) ? true : (index == arr.length-1) ? false : isEven(arr, index+1, 0, 0);
}
Other one was with the use of Navigable
map:
public static boolean isEven(NavigableMap<Integer, Integer> map) {
int left = 0;
int right = 0;
int n = map.size();
while(n-- > 0) {
left = right = 0;
for(Integer i : map.tailMap(n+1).values()) right += i;
for(Integer j : map.headMap(n).values()) left += j;
if (left == right) return true;
}
return false;
}
Here is how I read the input:
public static void main(String args) {
Scanner s = new Scanner(System.in);
final int N = s.nextInt();
for(int i = 0; i < N; i++) {
int NN = s.nextInt();
int arr = new int[NN];
for(int j = 0; j < NN; j++) {
arr[j] = s.nextInt();
}
System.out.println(isEven(arr, 0, 0, 0) ? "YES" : "NO");
}
}
To avoid an $O(n^2)$ solution, I can't check every element in the array, or can I?
java performance algorithm programming-challenge search
java performance algorithm programming-challenge search
edited Jul 29 '16 at 14:23
Pimgd
21.3k557142
21.3k557142
asked Jun 14 '15 at 21:02
Nilzone-Nilzone-
79111124
79111124
2
$begingroup$
@Vogel612 "Code Review is about improving existing, working code". My code does work. I just need to improve it's speed.
$endgroup$
– Nilzone-
Jun 14 '15 at 21:11
$begingroup$
fuu... sorry I missed the "timeout" in the issues statement, my bad. Are all other test-cases going through cleanly?
$endgroup$
– Vogel612♦
Jun 14 '15 at 21:16
$begingroup$
@Vogel612. Yes. I can provide a screenshot if you'd like.
$endgroup$
– Nilzone-
Jun 14 '15 at 21:17
1
$begingroup$
no need, I trust you, and skimming over the code looks like it should work ;)
$endgroup$
– Vogel612♦
Jun 14 '15 at 21:18
add a comment |
2
$begingroup$
@Vogel612 "Code Review is about improving existing, working code". My code does work. I just need to improve it's speed.
$endgroup$
– Nilzone-
Jun 14 '15 at 21:11
$begingroup$
fuu... sorry I missed the "timeout" in the issues statement, my bad. Are all other test-cases going through cleanly?
$endgroup$
– Vogel612♦
Jun 14 '15 at 21:16
$begingroup$
@Vogel612. Yes. I can provide a screenshot if you'd like.
$endgroup$
– Nilzone-
Jun 14 '15 at 21:17
1
$begingroup$
no need, I trust you, and skimming over the code looks like it should work ;)
$endgroup$
– Vogel612♦
Jun 14 '15 at 21:18
2
2
$begingroup$
@Vogel612 "Code Review is about improving existing, working code". My code does work. I just need to improve it's speed.
$endgroup$
– Nilzone-
Jun 14 '15 at 21:11
$begingroup$
@Vogel612 "Code Review is about improving existing, working code". My code does work. I just need to improve it's speed.
$endgroup$
– Nilzone-
Jun 14 '15 at 21:11
$begingroup$
fuu... sorry I missed the "timeout" in the issues statement, my bad. Are all other test-cases going through cleanly?
$endgroup$
– Vogel612♦
Jun 14 '15 at 21:16
$begingroup$
fuu... sorry I missed the "timeout" in the issues statement, my bad. Are all other test-cases going through cleanly?
$endgroup$
– Vogel612♦
Jun 14 '15 at 21:16
$begingroup$
@Vogel612. Yes. I can provide a screenshot if you'd like.
$endgroup$
– Nilzone-
Jun 14 '15 at 21:17
$begingroup$
@Vogel612. Yes. I can provide a screenshot if you'd like.
$endgroup$
– Nilzone-
Jun 14 '15 at 21:17
1
1
$begingroup$
no need, I trust you, and skimming over the code looks like it should work ;)
$endgroup$
– Vogel612♦
Jun 14 '15 at 21:18
$begingroup$
no need, I trust you, and skimming over the code looks like it should work ;)
$endgroup$
– Vogel612♦
Jun 14 '15 at 21:18
add a comment |
4 Answers
4
active
oldest
votes
$begingroup$
Your first example looks much nicer, so I'll focus on that.
First, let's remove the tail recursion in the most obvious way possible:
public static boolean isEven(int arr, int index, int leftSum, int rightSum) {
while (true) {
int i = index-1;
int j = index+1;
while(i > -1) {
leftSum += arr[i--];
}
while(j < arr.length) {
rightSum += arr[j++];
}
if (leftSum == rightSum) {
return true;
}
if (index == arr.length-1) {
return false
}
index += 1;
leftSum = 0;
rightSum = 0;
}
}
Now let's clean it up:
public static boolean isEven(int arr) {
for (int index = 0; index < arr.length; index++) {
int leftSum = 0;
for (int i = index - 1; i > -1; i--) {
leftSum += arr[i];
}
int rightSum = 0;
for (int i = index+1; i < arr.length; i++) {
rightSum += arr[i];
}
if (leftSum == rightSum) {
return true;
}
}
return false;
}
We can combine the sum variables:
public static boolean isEven(int arr) {
for (int index = 0; index < arr.length; index++) {
int difference = 0;
for (int i = index - 1; i > -1; i--) {
difference += arr[i];
}
for (int i = index+1; i < arr.length; i++) {
difference -= arr[i];
}
if (difference == 0) {
return true;
}
}
return false;
}
Now consider that we don't need to recalculate difference
each time. If one iteration we have
|-A-| * |--B--|
1 2 3 4 5 6 7 8
The next we have
|-A-|++ --|-B--|
1 2 3 4 5 6 7 8
Namely, we add 4 to A and subtract 5 from B, which means we add 4 and 5 to the difference. We should also check for empty arrays.
public static boolean isEven(int arr) {
if (arr.length == 0) {
// Alternatively, return false since there
// is no element that satisfies the condition.
throw new IllegalArgumentException();
}
int difference = arr[0] - Arrays.stream(arr).sum();
if (difference == 0) {
return true;
}
for (int i = 1; i < arr.length; i++) {
difference += arr[i-1];
difference += arr[i];
if (difference == 0) {
return true;
}
}
return false;
}
$endgroup$
$begingroup$
Nice suggestion, but it still times out on the same two test cases I'm having troubles with.
$endgroup$
– Nilzone-
Jun 14 '15 at 21:44
$begingroup$
@Nilzone- Are you sure it's this function that's the problem? This function should be very fast - certainly faster than parsing the input.
$endgroup$
– Veedrac
Jun 14 '15 at 21:45
$begingroup$
I updated the answer so you can see how I read the input.
$endgroup$
– Nilzone-
Jun 14 '15 at 21:47
$begingroup$
@Nilzone- It works for me. Are you sure you're not being tripped up by method overloading or something?
$endgroup$
– Veedrac
Jun 14 '15 at 22:02
$begingroup$
anything I'm missing here? pastebin.com/PKLHcrr2
$endgroup$
– Nilzone-
Jun 14 '15 at 22:04
|
show 4 more comments
$begingroup$
This what my code looks like. If the array is length 1, I put it in an if
statement, else the whole array needs to be traversed, saving some time.
Another important thing I have done is that while taking all the input, I have calculated the sum of them, as I am left traversing, then the sum of the array is actually rightSum
(rightSum
= sum - value of current index).
While I am traversing the left one increased value by adding previous index and right one decreases by the current index value.
// TODO code application logic here
Scanner lab = new Scanner(System.in);
int leftSum = 0;
int rightSum = 0;
int testCases = lab.nextInt();
for (int i = 0; i < testCases; i++) {
int length = lab.nextInt();
int temp = new int[length];
for (int j = 0; j < length; j++) {
temp[j] = lab.nextInt();
rightSum += temp[j];
}
if (length == 1) {
System.out.println("YES");
} else {
rightSum = rightSum - temp[0];
for (int j = 1; j < length; j++) {
if (j == length - 1) {
System.out.println("NO");
break;
}
rightSum = rightSum - temp[j];
leftSum = leftSum + temp[j - 1];
if (leftSum == rightSum) {
System.out.println("YES");
break;
}
}
}
rightSum = 0;
leftSum = 0;
}
$endgroup$
add a comment |
$begingroup$
Your performance problem is that you are redoing the same computations over and over again. You keep recomputing the running sums at the extremities. You should have a more intelligent algorithm that caches the running sums from both directions, or precomputes them. Those questions are very often about dynamic programming.
I was confused by the function name isEven
(I was thinking even/odd); I think isEqual
is better.
I don't get why isEven
has the function arguments leftSum
and rightSum
. Since they are always set to 0, they should just be variables within the method initialized to 0.
$endgroup$
$begingroup$
Should be noted that code for a linear time algorithm is presented in Veedrac's answer
$endgroup$
– VisualMelon
Aug 13 '17 at 10:43
add a comment |
$begingroup$
I have reviewed your code and found you are using two nested loops which are having O(n^2) complexity. There are multiple approaches to solve this problem but I will explain to you the most efficient way to solve this problem and 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 sides 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 the 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$
add a comment |
protected by Jamal♦ Aug 12 '17 at 17:37
Thank you for your interest in this question.
Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).
Would you like to answer one of these unanswered questions instead?
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Your first example looks much nicer, so I'll focus on that.
First, let's remove the tail recursion in the most obvious way possible:
public static boolean isEven(int arr, int index, int leftSum, int rightSum) {
while (true) {
int i = index-1;
int j = index+1;
while(i > -1) {
leftSum += arr[i--];
}
while(j < arr.length) {
rightSum += arr[j++];
}
if (leftSum == rightSum) {
return true;
}
if (index == arr.length-1) {
return false
}
index += 1;
leftSum = 0;
rightSum = 0;
}
}
Now let's clean it up:
public static boolean isEven(int arr) {
for (int index = 0; index < arr.length; index++) {
int leftSum = 0;
for (int i = index - 1; i > -1; i--) {
leftSum += arr[i];
}
int rightSum = 0;
for (int i = index+1; i < arr.length; i++) {
rightSum += arr[i];
}
if (leftSum == rightSum) {
return true;
}
}
return false;
}
We can combine the sum variables:
public static boolean isEven(int arr) {
for (int index = 0; index < arr.length; index++) {
int difference = 0;
for (int i = index - 1; i > -1; i--) {
difference += arr[i];
}
for (int i = index+1; i < arr.length; i++) {
difference -= arr[i];
}
if (difference == 0) {
return true;
}
}
return false;
}
Now consider that we don't need to recalculate difference
each time. If one iteration we have
|-A-| * |--B--|
1 2 3 4 5 6 7 8
The next we have
|-A-|++ --|-B--|
1 2 3 4 5 6 7 8
Namely, we add 4 to A and subtract 5 from B, which means we add 4 and 5 to the difference. We should also check for empty arrays.
public static boolean isEven(int arr) {
if (arr.length == 0) {
// Alternatively, return false since there
// is no element that satisfies the condition.
throw new IllegalArgumentException();
}
int difference = arr[0] - Arrays.stream(arr).sum();
if (difference == 0) {
return true;
}
for (int i = 1; i < arr.length; i++) {
difference += arr[i-1];
difference += arr[i];
if (difference == 0) {
return true;
}
}
return false;
}
$endgroup$
$begingroup$
Nice suggestion, but it still times out on the same two test cases I'm having troubles with.
$endgroup$
– Nilzone-
Jun 14 '15 at 21:44
$begingroup$
@Nilzone- Are you sure it's this function that's the problem? This function should be very fast - certainly faster than parsing the input.
$endgroup$
– Veedrac
Jun 14 '15 at 21:45
$begingroup$
I updated the answer so you can see how I read the input.
$endgroup$
– Nilzone-
Jun 14 '15 at 21:47
$begingroup$
@Nilzone- It works for me. Are you sure you're not being tripped up by method overloading or something?
$endgroup$
– Veedrac
Jun 14 '15 at 22:02
$begingroup$
anything I'm missing here? pastebin.com/PKLHcrr2
$endgroup$
– Nilzone-
Jun 14 '15 at 22:04
|
show 4 more comments
$begingroup$
Your first example looks much nicer, so I'll focus on that.
First, let's remove the tail recursion in the most obvious way possible:
public static boolean isEven(int arr, int index, int leftSum, int rightSum) {
while (true) {
int i = index-1;
int j = index+1;
while(i > -1) {
leftSum += arr[i--];
}
while(j < arr.length) {
rightSum += arr[j++];
}
if (leftSum == rightSum) {
return true;
}
if (index == arr.length-1) {
return false
}
index += 1;
leftSum = 0;
rightSum = 0;
}
}
Now let's clean it up:
public static boolean isEven(int arr) {
for (int index = 0; index < arr.length; index++) {
int leftSum = 0;
for (int i = index - 1; i > -1; i--) {
leftSum += arr[i];
}
int rightSum = 0;
for (int i = index+1; i < arr.length; i++) {
rightSum += arr[i];
}
if (leftSum == rightSum) {
return true;
}
}
return false;
}
We can combine the sum variables:
public static boolean isEven(int arr) {
for (int index = 0; index < arr.length; index++) {
int difference = 0;
for (int i = index - 1; i > -1; i--) {
difference += arr[i];
}
for (int i = index+1; i < arr.length; i++) {
difference -= arr[i];
}
if (difference == 0) {
return true;
}
}
return false;
}
Now consider that we don't need to recalculate difference
each time. If one iteration we have
|-A-| * |--B--|
1 2 3 4 5 6 7 8
The next we have
|-A-|++ --|-B--|
1 2 3 4 5 6 7 8
Namely, we add 4 to A and subtract 5 from B, which means we add 4 and 5 to the difference. We should also check for empty arrays.
public static boolean isEven(int arr) {
if (arr.length == 0) {
// Alternatively, return false since there
// is no element that satisfies the condition.
throw new IllegalArgumentException();
}
int difference = arr[0] - Arrays.stream(arr).sum();
if (difference == 0) {
return true;
}
for (int i = 1; i < arr.length; i++) {
difference += arr[i-1];
difference += arr[i];
if (difference == 0) {
return true;
}
}
return false;
}
$endgroup$
$begingroup$
Nice suggestion, but it still times out on the same two test cases I'm having troubles with.
$endgroup$
– Nilzone-
Jun 14 '15 at 21:44
$begingroup$
@Nilzone- Are you sure it's this function that's the problem? This function should be very fast - certainly faster than parsing the input.
$endgroup$
– Veedrac
Jun 14 '15 at 21:45
$begingroup$
I updated the answer so you can see how I read the input.
$endgroup$
– Nilzone-
Jun 14 '15 at 21:47
$begingroup$
@Nilzone- It works for me. Are you sure you're not being tripped up by method overloading or something?
$endgroup$
– Veedrac
Jun 14 '15 at 22:02
$begingroup$
anything I'm missing here? pastebin.com/PKLHcrr2
$endgroup$
– Nilzone-
Jun 14 '15 at 22:04
|
show 4 more comments
$begingroup$
Your first example looks much nicer, so I'll focus on that.
First, let's remove the tail recursion in the most obvious way possible:
public static boolean isEven(int arr, int index, int leftSum, int rightSum) {
while (true) {
int i = index-1;
int j = index+1;
while(i > -1) {
leftSum += arr[i--];
}
while(j < arr.length) {
rightSum += arr[j++];
}
if (leftSum == rightSum) {
return true;
}
if (index == arr.length-1) {
return false
}
index += 1;
leftSum = 0;
rightSum = 0;
}
}
Now let's clean it up:
public static boolean isEven(int arr) {
for (int index = 0; index < arr.length; index++) {
int leftSum = 0;
for (int i = index - 1; i > -1; i--) {
leftSum += arr[i];
}
int rightSum = 0;
for (int i = index+1; i < arr.length; i++) {
rightSum += arr[i];
}
if (leftSum == rightSum) {
return true;
}
}
return false;
}
We can combine the sum variables:
public static boolean isEven(int arr) {
for (int index = 0; index < arr.length; index++) {
int difference = 0;
for (int i = index - 1; i > -1; i--) {
difference += arr[i];
}
for (int i = index+1; i < arr.length; i++) {
difference -= arr[i];
}
if (difference == 0) {
return true;
}
}
return false;
}
Now consider that we don't need to recalculate difference
each time. If one iteration we have
|-A-| * |--B--|
1 2 3 4 5 6 7 8
The next we have
|-A-|++ --|-B--|
1 2 3 4 5 6 7 8
Namely, we add 4 to A and subtract 5 from B, which means we add 4 and 5 to the difference. We should also check for empty arrays.
public static boolean isEven(int arr) {
if (arr.length == 0) {
// Alternatively, return false since there
// is no element that satisfies the condition.
throw new IllegalArgumentException();
}
int difference = arr[0] - Arrays.stream(arr).sum();
if (difference == 0) {
return true;
}
for (int i = 1; i < arr.length; i++) {
difference += arr[i-1];
difference += arr[i];
if (difference == 0) {
return true;
}
}
return false;
}
$endgroup$
Your first example looks much nicer, so I'll focus on that.
First, let's remove the tail recursion in the most obvious way possible:
public static boolean isEven(int arr, int index, int leftSum, int rightSum) {
while (true) {
int i = index-1;
int j = index+1;
while(i > -1) {
leftSum += arr[i--];
}
while(j < arr.length) {
rightSum += arr[j++];
}
if (leftSum == rightSum) {
return true;
}
if (index == arr.length-1) {
return false
}
index += 1;
leftSum = 0;
rightSum = 0;
}
}
Now let's clean it up:
public static boolean isEven(int arr) {
for (int index = 0; index < arr.length; index++) {
int leftSum = 0;
for (int i = index - 1; i > -1; i--) {
leftSum += arr[i];
}
int rightSum = 0;
for (int i = index+1; i < arr.length; i++) {
rightSum += arr[i];
}
if (leftSum == rightSum) {
return true;
}
}
return false;
}
We can combine the sum variables:
public static boolean isEven(int arr) {
for (int index = 0; index < arr.length; index++) {
int difference = 0;
for (int i = index - 1; i > -1; i--) {
difference += arr[i];
}
for (int i = index+1; i < arr.length; i++) {
difference -= arr[i];
}
if (difference == 0) {
return true;
}
}
return false;
}
Now consider that we don't need to recalculate difference
each time. If one iteration we have
|-A-| * |--B--|
1 2 3 4 5 6 7 8
The next we have
|-A-|++ --|-B--|
1 2 3 4 5 6 7 8
Namely, we add 4 to A and subtract 5 from B, which means we add 4 and 5 to the difference. We should also check for empty arrays.
public static boolean isEven(int arr) {
if (arr.length == 0) {
// Alternatively, return false since there
// is no element that satisfies the condition.
throw new IllegalArgumentException();
}
int difference = arr[0] - Arrays.stream(arr).sum();
if (difference == 0) {
return true;
}
for (int i = 1; i < arr.length; i++) {
difference += arr[i-1];
difference += arr[i];
if (difference == 0) {
return true;
}
}
return false;
}
edited Jun 14 '15 at 21:46
answered Jun 14 '15 at 21:38
VeedracVeedrac
9,1931634
9,1931634
$begingroup$
Nice suggestion, but it still times out on the same two test cases I'm having troubles with.
$endgroup$
– Nilzone-
Jun 14 '15 at 21:44
$begingroup$
@Nilzone- Are you sure it's this function that's the problem? This function should be very fast - certainly faster than parsing the input.
$endgroup$
– Veedrac
Jun 14 '15 at 21:45
$begingroup$
I updated the answer so you can see how I read the input.
$endgroup$
– Nilzone-
Jun 14 '15 at 21:47
$begingroup$
@Nilzone- It works for me. Are you sure you're not being tripped up by method overloading or something?
$endgroup$
– Veedrac
Jun 14 '15 at 22:02
$begingroup$
anything I'm missing here? pastebin.com/PKLHcrr2
$endgroup$
– Nilzone-
Jun 14 '15 at 22:04
|
show 4 more comments
$begingroup$
Nice suggestion, but it still times out on the same two test cases I'm having troubles with.
$endgroup$
– Nilzone-
Jun 14 '15 at 21:44
$begingroup$
@Nilzone- Are you sure it's this function that's the problem? This function should be very fast - certainly faster than parsing the input.
$endgroup$
– Veedrac
Jun 14 '15 at 21:45
$begingroup$
I updated the answer so you can see how I read the input.
$endgroup$
– Nilzone-
Jun 14 '15 at 21:47
$begingroup$
@Nilzone- It works for me. Are you sure you're not being tripped up by method overloading or something?
$endgroup$
– Veedrac
Jun 14 '15 at 22:02
$begingroup$
anything I'm missing here? pastebin.com/PKLHcrr2
$endgroup$
– Nilzone-
Jun 14 '15 at 22:04
$begingroup$
Nice suggestion, but it still times out on the same two test cases I'm having troubles with.
$endgroup$
– Nilzone-
Jun 14 '15 at 21:44
$begingroup$
Nice suggestion, but it still times out on the same two test cases I'm having troubles with.
$endgroup$
– Nilzone-
Jun 14 '15 at 21:44
$begingroup$
@Nilzone- Are you sure it's this function that's the problem? This function should be very fast - certainly faster than parsing the input.
$endgroup$
– Veedrac
Jun 14 '15 at 21:45
$begingroup$
@Nilzone- Are you sure it's this function that's the problem? This function should be very fast - certainly faster than parsing the input.
$endgroup$
– Veedrac
Jun 14 '15 at 21:45
$begingroup$
I updated the answer so you can see how I read the input.
$endgroup$
– Nilzone-
Jun 14 '15 at 21:47
$begingroup$
I updated the answer so you can see how I read the input.
$endgroup$
– Nilzone-
Jun 14 '15 at 21:47
$begingroup$
@Nilzone- It works for me. Are you sure you're not being tripped up by method overloading or something?
$endgroup$
– Veedrac
Jun 14 '15 at 22:02
$begingroup$
@Nilzone- It works for me. Are you sure you're not being tripped up by method overloading or something?
$endgroup$
– Veedrac
Jun 14 '15 at 22:02
$begingroup$
anything I'm missing here? pastebin.com/PKLHcrr2
$endgroup$
– Nilzone-
Jun 14 '15 at 22:04
$begingroup$
anything I'm missing here? pastebin.com/PKLHcrr2
$endgroup$
– Nilzone-
Jun 14 '15 at 22:04
|
show 4 more comments
$begingroup$
This what my code looks like. If the array is length 1, I put it in an if
statement, else the whole array needs to be traversed, saving some time.
Another important thing I have done is that while taking all the input, I have calculated the sum of them, as I am left traversing, then the sum of the array is actually rightSum
(rightSum
= sum - value of current index).
While I am traversing the left one increased value by adding previous index and right one decreases by the current index value.
// TODO code application logic here
Scanner lab = new Scanner(System.in);
int leftSum = 0;
int rightSum = 0;
int testCases = lab.nextInt();
for (int i = 0; i < testCases; i++) {
int length = lab.nextInt();
int temp = new int[length];
for (int j = 0; j < length; j++) {
temp[j] = lab.nextInt();
rightSum += temp[j];
}
if (length == 1) {
System.out.println("YES");
} else {
rightSum = rightSum - temp[0];
for (int j = 1; j < length; j++) {
if (j == length - 1) {
System.out.println("NO");
break;
}
rightSum = rightSum - temp[j];
leftSum = leftSum + temp[j - 1];
if (leftSum == rightSum) {
System.out.println("YES");
break;
}
}
}
rightSum = 0;
leftSum = 0;
}
$endgroup$
add a comment |
$begingroup$
This what my code looks like. If the array is length 1, I put it in an if
statement, else the whole array needs to be traversed, saving some time.
Another important thing I have done is that while taking all the input, I have calculated the sum of them, as I am left traversing, then the sum of the array is actually rightSum
(rightSum
= sum - value of current index).
While I am traversing the left one increased value by adding previous index and right one decreases by the current index value.
// TODO code application logic here
Scanner lab = new Scanner(System.in);
int leftSum = 0;
int rightSum = 0;
int testCases = lab.nextInt();
for (int i = 0; i < testCases; i++) {
int length = lab.nextInt();
int temp = new int[length];
for (int j = 0; j < length; j++) {
temp[j] = lab.nextInt();
rightSum += temp[j];
}
if (length == 1) {
System.out.println("YES");
} else {
rightSum = rightSum - temp[0];
for (int j = 1; j < length; j++) {
if (j == length - 1) {
System.out.println("NO");
break;
}
rightSum = rightSum - temp[j];
leftSum = leftSum + temp[j - 1];
if (leftSum == rightSum) {
System.out.println("YES");
break;
}
}
}
rightSum = 0;
leftSum = 0;
}
$endgroup$
add a comment |
$begingroup$
This what my code looks like. If the array is length 1, I put it in an if
statement, else the whole array needs to be traversed, saving some time.
Another important thing I have done is that while taking all the input, I have calculated the sum of them, as I am left traversing, then the sum of the array is actually rightSum
(rightSum
= sum - value of current index).
While I am traversing the left one increased value by adding previous index and right one decreases by the current index value.
// TODO code application logic here
Scanner lab = new Scanner(System.in);
int leftSum = 0;
int rightSum = 0;
int testCases = lab.nextInt();
for (int i = 0; i < testCases; i++) {
int length = lab.nextInt();
int temp = new int[length];
for (int j = 0; j < length; j++) {
temp[j] = lab.nextInt();
rightSum += temp[j];
}
if (length == 1) {
System.out.println("YES");
} else {
rightSum = rightSum - temp[0];
for (int j = 1; j < length; j++) {
if (j == length - 1) {
System.out.println("NO");
break;
}
rightSum = rightSum - temp[j];
leftSum = leftSum + temp[j - 1];
if (leftSum == rightSum) {
System.out.println("YES");
break;
}
}
}
rightSum = 0;
leftSum = 0;
}
$endgroup$
This what my code looks like. If the array is length 1, I put it in an if
statement, else the whole array needs to be traversed, saving some time.
Another important thing I have done is that while taking all the input, I have calculated the sum of them, as I am left traversing, then the sum of the array is actually rightSum
(rightSum
= sum - value of current index).
While I am traversing the left one increased value by adding previous index and right one decreases by the current index value.
// TODO code application logic here
Scanner lab = new Scanner(System.in);
int leftSum = 0;
int rightSum = 0;
int testCases = lab.nextInt();
for (int i = 0; i < testCases; i++) {
int length = lab.nextInt();
int temp = new int[length];
for (int j = 0; j < length; j++) {
temp[j] = lab.nextInt();
rightSum += temp[j];
}
if (length == 1) {
System.out.println("YES");
} else {
rightSum = rightSum - temp[0];
for (int j = 1; j < length; j++) {
if (j == length - 1) {
System.out.println("NO");
break;
}
rightSum = rightSum - temp[j];
leftSum = leftSum + temp[j - 1];
if (leftSum == rightSum) {
System.out.println("YES");
break;
}
}
}
rightSum = 0;
leftSum = 0;
}
edited Aug 12 '17 at 17:40
Jamal♦
30.4k11121227
30.4k11121227
answered Sep 9 '16 at 17:44
Koushik JayKoushik Jay
112
112
add a comment |
add a comment |
$begingroup$
Your performance problem is that you are redoing the same computations over and over again. You keep recomputing the running sums at the extremities. You should have a more intelligent algorithm that caches the running sums from both directions, or precomputes them. Those questions are very often about dynamic programming.
I was confused by the function name isEven
(I was thinking even/odd); I think isEqual
is better.
I don't get why isEven
has the function arguments leftSum
and rightSum
. Since they are always set to 0, they should just be variables within the method initialized to 0.
$endgroup$
$begingroup$
Should be noted that code for a linear time algorithm is presented in Veedrac's answer
$endgroup$
– VisualMelon
Aug 13 '17 at 10:43
add a comment |
$begingroup$
Your performance problem is that you are redoing the same computations over and over again. You keep recomputing the running sums at the extremities. You should have a more intelligent algorithm that caches the running sums from both directions, or precomputes them. Those questions are very often about dynamic programming.
I was confused by the function name isEven
(I was thinking even/odd); I think isEqual
is better.
I don't get why isEven
has the function arguments leftSum
and rightSum
. Since they are always set to 0, they should just be variables within the method initialized to 0.
$endgroup$
$begingroup$
Should be noted that code for a linear time algorithm is presented in Veedrac's answer
$endgroup$
– VisualMelon
Aug 13 '17 at 10:43
add a comment |
$begingroup$
Your performance problem is that you are redoing the same computations over and over again. You keep recomputing the running sums at the extremities. You should have a more intelligent algorithm that caches the running sums from both directions, or precomputes them. Those questions are very often about dynamic programming.
I was confused by the function name isEven
(I was thinking even/odd); I think isEqual
is better.
I don't get why isEven
has the function arguments leftSum
and rightSum
. Since they are always set to 0, they should just be variables within the method initialized to 0.
$endgroup$
Your performance problem is that you are redoing the same computations over and over again. You keep recomputing the running sums at the extremities. You should have a more intelligent algorithm that caches the running sums from both directions, or precomputes them. Those questions are very often about dynamic programming.
I was confused by the function name isEven
(I was thinking even/odd); I think isEqual
is better.
I don't get why isEven
has the function arguments leftSum
and rightSum
. Since they are always set to 0, they should just be variables within the method initialized to 0.
answered Aug 12 '17 at 19:04
toto2toto2
5,1871119
5,1871119
$begingroup$
Should be noted that code for a linear time algorithm is presented in Veedrac's answer
$endgroup$
– VisualMelon
Aug 13 '17 at 10:43
add a comment |
$begingroup$
Should be noted that code for a linear time algorithm is presented in Veedrac's answer
$endgroup$
– VisualMelon
Aug 13 '17 at 10:43
$begingroup$
Should be noted that code for a linear time algorithm is presented in Veedrac's answer
$endgroup$
– VisualMelon
Aug 13 '17 at 10:43
$begingroup$
Should be noted that code for a linear time algorithm is presented in Veedrac's answer
$endgroup$
– VisualMelon
Aug 13 '17 at 10:43
add a comment |
$begingroup$
I have reviewed your code and found you are using two nested loops which are having O(n^2) complexity. There are multiple approaches to solve this problem but I will explain to you the most efficient way to solve this problem and 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 sides 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 the 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$
add a comment |
$begingroup$
I have reviewed your code and found you are using two nested loops which are having O(n^2) complexity. There are multiple approaches to solve this problem but I will explain to you the most efficient way to solve this problem and 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 sides 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 the 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$
add a comment |
$begingroup$
I have reviewed your code and found you are using two nested loops which are having O(n^2) complexity. There are multiple approaches to solve this problem but I will explain to you the most efficient way to solve this problem and 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 sides 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 the 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$
I have reviewed your code and found you are using two nested loops which are having O(n^2) complexity. There are multiple approaches to solve this problem but I will explain to you the most efficient way to solve this problem and 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 sides 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 the 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.
answered 17 mins ago
KanahaiyaKanahaiya
493
493
add a comment |
add a comment |
protected by Jamal♦ Aug 12 '17 at 17:37
Thank you for your interest in this question.
Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).
Would you like to answer one of these unanswered questions instead?
2
$begingroup$
@Vogel612 "Code Review is about improving existing, working code". My code does work. I just need to improve it's speed.
$endgroup$
– Nilzone-
Jun 14 '15 at 21:11
$begingroup$
fuu... sorry I missed the "timeout" in the issues statement, my bad. Are all other test-cases going through cleanly?
$endgroup$
– Vogel612♦
Jun 14 '15 at 21:16
$begingroup$
@Vogel612. Yes. I can provide a screenshot if you'd like.
$endgroup$
– Nilzone-
Jun 14 '15 at 21:17
1
$begingroup$
no need, I trust you, and skimming over the code looks like it should work ;)
$endgroup$
– Vogel612♦
Jun 14 '15 at 21:18