Calculating diagonal difference

Question

I was trying to solve a problem concerning the difference of the diagonal sums of a matrix (using C99):

#include<stdio.h>

int main(){
    /*n: is the size of the matrix (squared matrix) and it is Entered by the user*/
    int n,line,row,sum_one=0,sum_two=0,dif;
    scanf("%i",&n);
    int array[n+1][n+1];

    for(line=1;line<=n;line++){
        for(row=1;row<=n;row++){
             scanf("%d",&array[line][row]);
        }
     }

     row = n;
     for(line=n;line>=1;line--){
            sum_one=sum_one+array[line][row];
            row--;
     }
     row = n;
     for(line=1;line<=n;line++){
            sum_two=sum_two+array[line][row];
            row--;
     }
     dif = sum_one-sum_two;
     if(dif<0){
         dif = -dif;
     }
     printf("%d \n",dif);
     return 0;
}

But I get in some testcases "terminated due to time out". Is there an efficient way than this algorithm?

Answer 1

There are a number of things that you can do to improve your code.

Understand C arrays

In C, arrays are zero based, so the first element of array is array[0] not array[1]. A number of other things follow from that.

Use whitespace to improve readability

Lines like this:

for(line=1;line<=n;line++){

become much easier to read with a little bit of whitespace:

for (line = 1; line <= n; line++) {

Choose better variable names

Names like line and row are descriptive, but the name array is not so good. Consider matrix or some other better name.

Use idiomatic C

The code currently includes this line:

for(line=1;line<=n;line++){

But since arrays are zero-based, as mentioned above, the C idiom would be this:

for (line = 0; line < n; line++) {

Similarly, instead of this:

sum_two=sum_two+array[line][row];

Write this:

sum_two += array[line][row];

Consider eliminating variables

The variable dif is only used at the very end of the program. Since it's really the calculation of this number that is the point of the program, it you don't really need to separately keep sum_one and sum_two. For example the second calculating for loop could be written like this:

for (line = 0; line < n; line++) {
    dif -= array[line][row];
    row--;
}

Check return values for errors

The call to scanf can fail. You must check the return values to make sure they haven't or your program may crash (or worse) when given malformed input. Rigorous error handling is the difference between mostly working and bug-free software. You should strive for the latter.

Decompose your program into functions

All of the logic here is in main in one rather long and dense chunk of code. It would be better to decompose this into separate functions.

Avoid scanf if you can

There are so many well known problems with scanf that you're usually better off avoiding it. A better way to handle this would probably be to input a char array (a string in C) and then parse that. This would allow the code to handle the case that the number input by the user for the array size is not a number. The current code loops infinitely when that happens.

Consider separating input and output

Right now, the main function reads in the the matrix, and then performs the calculation and then prints the result of the matrix calculation. A more modular (and likely more maintainable) approach would separate these into separate functions.

Consider more memory efficient calculation

In the current code, the entire matrix is stored in memory even though most elements are never used. Consider instead that the calculation could be done as each line is read, and then the input line discarded. For very large matrices this could make a significant difference in storage space required by this program.

Eliminate return 0 at the end of main

Since C99, the compiler automatically generates the code corresponding to return 0 at the end of main so there is no need to explicitly write it.