7
\$\begingroup\$

hackerrank.com - diagonal difference:

Problem Statement

You are given a square matrix of size N×N. Calculate the absolute difference of the sums across the two main diagonals.

Input Format

The first line contains a single integer N. The next N lines contain N integers (each) describing the matrix.

Constraints

  • \$1 \le N \le 100\$
  • \$−100 \le A[i] \le 100\$

Output Format

Output a single integer equal to the absolute difference in the sums across the diagonals.

Sample Input

3
11 2 4
4 5 6
10 8 -12

Sample Output

15

Explanation

The first diagonal of the matrix is:

11
    5
        -12

Sum across the first diagonal = 11+5-12= 4

The second diagonal of the matrix is:

        4
    5
10

Sum across the second diagonal = 4+5+10 = 19

Difference: |4-19| =15

How can this solution be improved?

function processData(input) {
    inputAll = input.split("\n");
    var currentLine = 0;
    var numberOfInputs = parseInt(inputAll[currentLine].trim(), 10);

    currentLine = 1;
    var sumFirstDiagonal = 0;
    var sumSecondDiagonal = 0;
    var difference = 0;
    for(currentLine = 1 ; currentLine <= numberOfInputs ; currentLine++)
        {
            var inputs = inputAll[currentLine];
            var inputArray = inputs.split(" ");


            for(var i=0 ; i<=(numberOfInputs-1);i++)
                {
                    if(i == (currentLine - 1))
                        {

                            sumFirstDiagonal = sumFirstDiagonal + parseInt(inputArray[i]);
                        }
                }

            for(var j=(numberOfInputs-1) ; j>=0;j--)
                {
                    if(j ==  ( (numberOfInputs - 1) - (currentLine - 1)))
                        {

                            sumSecondDiagonal = sumSecondDiagonal + parseInt(inputArray[j]);
                        }
                }

        }
    difference = sumFirstDiagonal - sumSecondDiagonal;
    difference = Math.abs(difference);
    process.stdout.write(""+difference+"\n");
}
\$\endgroup\$
10
\$\begingroup\$

You don't need the inner for loops because you know exactly which array element you want for each sum:

for(currentLine = 1 ; currentLine <= numberOfInputs ; currentLine++)
    {
        var inputs = inputAll[currentLine];
        var inputArray = inputs.split(" ");

        sumFirstDiagonal += parseInt( inputArray[ currentLine - 1 ])
        sumSecondDiagonal += parseInt (inputArray [ inputArray.length - currentLine ])

    }
\$\endgroup\$
8
\$\begingroup\$

You're basically doing a lot of unnecessary work.

For instance, you don't need to calculate the diagonals individually and then subtract. That's taking the task too literally, when all that matters is the result. So just add and subtract along the way.

And as ErikR says, the inner loops really aren't necessary, since you know the index you want. Your ifs basically mean that the loops only do something once in their runs, namely when the index is a known value. So since you know that value, you don't need the loops at all.

Anyway, this is a good use case for reduce:

function processData(input) {
  var rows = input.trim().split(/\n/),
      n = 1 * rows.shift(),
      sum;

  sum = rows.reduce(function (sum, row, i) {
    var values = row.split(/\s+/);
    return sum + (1 * values[i] - values[n - i - 1]);
  }, 0);

  return Math.abs(sum);
}

The above starts by shifting the first line off the array, and converts it to a number by multiplying by 1. The multiplication makes JS coerce the string to a number.

A similar trick is used in the reduce callback. 1 * string becomes a number, and number - string causes the second string to also be coerced into a number.


Alternatively, you can read everything as one long array of values, and loop through them, only picking out the indices you want:

function processData(input) {
  var values = input.trim().split(/\s+/), // split on all whitespace, including newlines
      n = 1 * values.shift(),
      sum = 0,
      i, offset;

  for(i = 0 ; i < n ; i++) {
    offset = n * i;
    sum += values[i + offset] - values[offset + n - i - 1];
  }

  return Math.abs(sum)
}

We don't even need to multiply by 1 inside the loop in this one, since string - string => number.

The above can also be written like this, which is probably clearer (and maybe even be a teeny, tiny bit faster):

function processData(input) {
  var values = input.trim().split(/\s+/),
      n = 1 * values.shift(),
      sum = 0,
      d1 = 0,     // first diagonal's starting index
      d2 = n - 1; // second diagonal's starting index

  while(d1 < values.length) {
    sum += values[d1] - values[d2];
    d1 += n + 1; // move down 1 row, and right by 1 column
    d2 += n - 1; // move down 1 row, and left by 1 column
  }

  return Math.abs(sum)
}
\$\endgroup\$
  • 2
    \$\begingroup\$ It's gotten to the point where I all I have to do is look at a short snippet to know it's a Flambino, because it's exactly what I'd do, except sometimes a little better. \$\endgroup\$ – Jonah Jan 2 '16 at 2:08
  • \$\begingroup\$ This should be the answer \$\endgroup\$ – Timur Mamedov Dec 19 '16 at 12:28
  • 1
    \$\begingroup\$ One note: currently on HackerRank's challenge for this algorithm, you don't have to convert the multi-line literal string to an array...a matrix of arrays is already created for you...thus Flambino's strategy can be slightly modified to accomplish passing all test cases! This was a great resource and got me through where I was stuck, thank you Flambino! \$\endgroup\$ – twknab Jan 1 '18 at 4:41
2
\$\begingroup\$

Note: The current HackerRank provides an input that is an array of arrays, each interior array being a row.

Example input:

11 2 4
4 5 6
10 8 -12

Output

[
    [11,2,4],
    [4,5,6],
    [10,8,-12]
]

Given this input you really don't have to do much. Since it's diagonal we can use the same index to select the row and the value within the row. You want the reversed position for the value on the second set of values, so simply reverse inline and add them together.

const input = [[11,2,4],[4,5,6],[10,8,-12]];
// Complete the diagonalDifference function below.
function diagonalDifference(arr) {
    let sum = 0;
    for (var i = 0; i <= arr.length - 1; i++) {
        sum += arr[i][i] - arr[i].reverse()[i];
    }
    return Math.abs(sum);
}
console.log(diagonalDifference(input));

That's pretty verbose of course. We can use a reduce and do it on one line.

function diagonalDifference(arr) {
    return Math.abs(arr.reduce((s, r, i) => s += r[i] - r.reverse()[i], 0));
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Can you please explain this part of your code? r[i] - r.reverse()[i] \$\endgroup\$ – Oke Tega Feb 20 at 4:56
  • \$\begingroup\$ It is the same as reversing the index. I just reversed the array instead of the index. \$\endgroup\$ – Jhawins Feb 20 at 19:14
  • \$\begingroup\$ You could replace it with r[i] - r[r.length - 1 - i] \$\endgroup\$ – Jhawins Feb 20 at 19:21

protected by Community Jul 25 '16 at 21:21

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?

Not the answer you're looking for? Browse other questions tagged or ask your own question.