bikky barnwal bikky barnwal - 2 months ago 22
Javascript Question

javascript hackerranks sherlock and array performance issue


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);
});

Answer

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>