bikky barnwal - 1 year ago 110

Javascript Question

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,

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.

Constraints

`1<=T<=10`

1<=N<=10^5

1<=Ai<=2*10^4

1<=i<=N

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.

Sample Input

`2`

3

1 2 3

4

1 2 3 3

Sample Output

`NO`

YES

Explanation

For the first test case, no such index exists. For the second test

case,

therefore index 3 satisfies the given conditions.

I'm having timeout issues on 3 of the test cases

`function check(input) {`

var result = "NO";

var sum=0;

input.map(function(data){

sum=sum+(+data);

})

sumLeft=0;

sumRight=sum-(+input[0]);

for(var i=1;i<input.length;i++){

sumLeft=sumLeft+(+input[i-1]);

sumRight=sumRight-(+input[i])

if(sumLeft==sumRight)

{

console.log("YES");

return;

}

}

console.log("NO");

}

function processData(input) {

//Enter your code here

var lines = input.split("\r\n");

for (var m = 2; m < lines.length; m = m + 2) {

check(lines[m].split(" "));

}

}

process.stdin.resume();

process.stdin.setEncoding("ascii");

_input = "";

process.stdin.on("data", function(input) {

_input += input;

});

process.stdin.on("end", function() {

processData(_input);

});

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

You could go through the array from both ends in inwards direction using two pointers (indices). Keep a balance, starting with 0, as follows:

When the balance is negative move the left pointer one step to the right while increasing the balance with the value you leave behind. When the balance is positive, move the right pointer one step to the left while decreasing the balance with the value you leave behind.

When the two pointers meet each other, check the balance. If it is zero, you have success.

Here is the algorithm in ES6 code, together with a text area where you can adapt the input according to the required input format:

```
function hasMiddle(a) {
var balance = 0, i = 0, j = a.length-1;
while (i < j) balance += balance > 0 ? -a[j--] : a[i++];
return !balance;
}
// I/O: event handling, parsing input, formatting output
var input = document.querySelector('textarea');
var output = document.querySelector('pre');
input.oninput = function() {
var lines = this.value.trim().split(/[\r\n]+/).filter(s => s.trim().length);
// Strip the case count and array element counts:
lines = lines.slice(1).filter( (s, i) => i % 2 );
// Call function for each test case, returning array of booleans:
var results = lines.map( line => hasMiddle(line.match(/\d+/g).map(Number)) );
// Output results
output.textContent = results.map( pos => pos ? 'YES' : 'NO' ).join('\n');
}
// Evaluate input immediately
input.oninput();
```

```
Input:<br>
<textarea style="width:100%; height:120px">2
3
1 2 3
4
1 2 3 3
</textarea>
<pre></pre>
```

This algorithm requires your input array to consist of non-negative numbers.

If you need to support negative numbers in your array, then the algorithm needs to go through the array first to calculate the sum, and then go through the array again to find the point where the balance reaches 0:

```
function hasMiddle(a) {
var balance = a.reduce( (sum, v) => sum + v );
return !a.every ( (v, i) => balance -= v + (i ? a[i-1] : 0) );
}
// I/O for snippet
var input = document.querySelector('textarea');
var output = document.querySelector('pre');
input.oninput = function() {
var lines = this.value.trim().split(/[\r\n]+/).filter(s => s.trim().length);
// Strip the case count and array element counts:
lines = lines.slice(1).filter( (s, i) => i % 2 );
// Call function for each test case, returning array of booleans:
var results = lines.map( line => hasMiddle(line.match(/[\d-]+/g).map(Number)));
// Output results
output.textContent = results.map( pos => pos ? 'YES' : 'NO' ).join('\n');
}
// Evaluate input immediately
input.oninput();
```

```
Input:<br>
<textarea style="width:100%; height:120px">2
3
1 2 3
4
1 2 3 3
</textarea>
<pre></pre>
```

Recommended from our users: **Dynamic Network Monitoring from WhatsUp Gold from IPSwitch**. ** Free Download**