We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
surely your way of solution is quite good
it saves a lot of space
but if look 4 time it is not a cool solution if the number for matrix N is too high then for each entry there will be condition checking goes timely too much costly.
This solution is actually asymptotically optimal for time as well as space, a certain amount of condition checking calculations would be required for ANY solution to this problem, and the overhead of storing data to an array is much higher than doing a simple condition check on data that is already loaded into computation registers while iterating through the loop (so your argument makes no sense). To use an array, which is what it seems like you are suggesting as a better solution, would just add several layers of inefficiency and could result in additional computation time as N becomes large due to the overhead involved in needlessly storing and reloading inputs that are not needed for calculation and are not needed beyond a single calculation. Using an array also becomes increasingly inefficient as N grows, because the more space you block out (the larger the array), the harder it is to find contiguous space in memory to store that array (so a lot of behind-the-scenes time consuming data shuffling takes place).
You are absolutely right. That being said, sometimes it may be better to write code that exhibits explicitly its logic, here "summing the elements of the diagonal of a square matrix" and for this purpose using a 2-D array could be better here I guess.
But yes, when it comes to performances, storing data used only once is clearly ineffective.
In software engineering, algorithms get complex; part of being a good programmer is breaking down things into structured components and providing adequate documentation for your work, to both ensure you fully understand why what you did works and so others can better understand it during code review. Using an array for this is an incredibly sloppy thing to do, because there is no need for it and you would still need an algorithm to calculate the values in the array--you should not add layers of complexity to your code that have no benefit. The only reason to use an array for this type of thing would be if you knew there would be a future need to perform additional calculations on the same set of data. At my job, an attempt to use an array for something like this would be kicked back in a code review and never make it to release.
IMHO, I would preffer saying "it depends", if I had to reuse this code for some reason,it would be written as a function or a method, in this case the array would be provided as a parameter, therefore storing it is not an option, it is mandatory.
Another scenario would be calculating the difference as part of the processing, as you've mentioned.
But I defenitely agree that to solve this specific problem you don't need to store the information.
Well, you don't need to use the array, only the diagonals, as the task is very specific. Building on the idea that we might need to use the array later feels like a cop-out to explain bad coding. If you'd need to use the array values, you would be given a different task, not this one.
My solution used an array as the default template code (C++) provided such. Looking at various discussions of solutions to HR problems, it seems as if we're encouraged to remove the template code and just write our own solution. I'm sure it's mentioned somewhere.
If the task is to demonstrate algorithm skills then developers should be encouraged to start fresh. If however, the task is to demonstrate ability to process/manipulate an array or STL vector, then the best way would be to upgrade the HR testing system to just provide an interface (with the main hidden elsewhere). This would also mean coders don't have to deal with string streams for every single test. e.g.
classSolution:publicISolution{private:intevaluate(conststd::vector<std::vector<int>>&input){// implement solution here //}};
// focus on the intended problem, no need to think and waste times with string streams, cout & cin.
codingbat.com works like that, you just write the function - saves the hassle of writing basic stuff. On the other hand for people learning a language here, it helps a lot for these basics to burn in their memories.
I don't believe any condition checking is required. The elements required to perform the calculations are fixed and the index of a for-loop can be used to access the correct row values, notwithstanding using an array or not.
The required condition check is the FOR condition; the algorithm checks the index of the current iteration in the FOR loop and performs an appropriate action (skip data, use in calculation, increment counter, end loop execution).
condition checking for FOR loop conditions is trivial because of compilers optimizations. OP has additional condition checking that is not optimal. And you clearly implied that it was necessary.
Performing constant time operations n2 times (the number of iterations of the loop) is, by definition, not trivial when discussing running time. The act of saving data to an array could be considered trivial, because it's an additional O(1) time operation within the loop.
You've actually got 3xN conditions, counting all your loops, but I like your thinking.
Here's my solution from JavaScript:
var n = parseInt(readLine());
var suma = 0, sumb = 0;
for(var i = 0; i < n; i++){
var line = readLine().split(' ');
suma += Number(line[i]);
sumb += Number(line[n-i-1]);
}
console.log(Math.abs(sumb-suma));
Hey there i'm pretty newbie and don't quite understand what the vectors are for and what they are doing, and if you could also explainwhat is going on with your third FOR statement i would appreciate it. Thanks in advance.
Yes it is in Java, many other languages have some version of split though. Scala and Python have split() that works in the same way, C has str_tok <- apparently works like split
AlissonP, this discussion of inefficiency due to storing useless information actually shouldn't be the focus here, please note that the problem statement says "Given a square matrix of size N x N, calculate the absolute difference between the sums of its diagonals.".
Diagonal Difference
You are viewing a single comment's thread. Return to all comments →
surely your way of solution is quite good it saves a lot of space but if look 4 time it is not a cool solution if the number for matrix N is too high then for each entry there will be condition checking goes timely too much costly.
This solution is actually asymptotically optimal for time as well as space, a certain amount of condition checking calculations would be required for ANY solution to this problem, and the overhead of storing data to an array is much higher than doing a simple condition check on data that is already loaded into computation registers while iterating through the loop (so your argument makes no sense). To use an array, which is what it seems like you are suggesting as a better solution, would just add several layers of inefficiency and could result in additional computation time as N becomes large due to the overhead involved in needlessly storing and reloading inputs that are not needed for calculation and are not needed beyond a single calculation. Using an array also becomes increasingly inefficient as N grows, because the more space you block out (the larger the array), the harder it is to find contiguous space in memory to store that array (so a lot of behind-the-scenes time consuming data shuffling takes place).
You are absolutely right. That being said, sometimes it may be better to write code that exhibits explicitly its logic, here "summing the elements of the diagonal of a square matrix" and for this purpose using a 2-D array could be better here I guess.
But yes, when it comes to performances, storing data used only once is clearly ineffective.
In software engineering, algorithms get complex; part of being a good programmer is breaking down things into structured components and providing adequate documentation for your work, to both ensure you fully understand why what you did works and so others can better understand it during code review. Using an array for this is an incredibly sloppy thing to do, because there is no need for it and you would still need an algorithm to calculate the values in the array--you should not add layers of complexity to your code that have no benefit. The only reason to use an array for this type of thing would be if you knew there would be a future need to perform additional calculations on the same set of data. At my job, an attempt to use an array for something like this would be kicked back in a code review and never make it to release.
IMHO, I would preffer saying "it depends", if I had to reuse this code for some reason,it would be written as a function or a method, in this case the array would be provided as a parameter, therefore storing it is not an option, it is mandatory.
Another scenario would be calculating the difference as part of the processing, as you've mentioned.
But I defenitely agree that to solve this specific problem you don't need to store the information.
Well, you don't need to use the array, only the diagonals, as the task is very specific. Building on the idea that we might need to use the array later feels like a cop-out to explain bad coding. If you'd need to use the array values, you would be given a different task, not this one.
My solution used an array as the default template code (C++) provided such. Looking at various discussions of solutions to HR problems, it seems as if we're encouraged to remove the template code and just write our own solution. I'm sure it's mentioned somewhere.
If the task is to demonstrate algorithm skills then developers should be encouraged to start fresh. If however, the task is to demonstrate ability to process/manipulate an array or STL vector, then the best way would be to upgrade the HR testing system to just provide an interface (with the main hidden elsewhere). This would also mean coders don't have to deal with string streams for every single test. e.g.
// focus on the intended problem, no need to think and waste times with string streams, cout & cin.
Just my two cents.
codingbat.com works like that, you just write the function - saves the hassle of writing basic stuff. On the other hand for people learning a language here, it helps a lot for these basics to burn in their memories.
I don't believe any condition checking is required. The elements required to perform the calculations are fixed and the index of a for-loop can be used to access the correct row values, notwithstanding using an array or not.
The required condition check is the FOR condition; the algorithm checks the index of the current iteration in the FOR loop and performs an appropriate action (skip data, use in calculation, increment counter, end loop execution).
condition checking for FOR loop conditions is trivial because of compilers optimizations. OP has additional condition checking that is not optimal. And you clearly implied that it was necessary.
Performing constant time operations n2 times (the number of iterations of the loop) is, by definition, not trivial when discussing running time. The act of saving data to an array could be considered trivial, because it's an additional O(1) time operation within the loop.
You do not need to have any conditions to complete this problem.
Because the diagonal are always going to be positions we know when we have the size of the matrix.
You've actually got 3xN conditions, counting all your loops, but I like your thinking.
Here's my solution from JavaScript:
Brilliant
Excellent!! My code have problem, the problem is because not use Math.abs!
Excellent Work. :D
Hey there i'm pretty newbie and don't quite understand what the vectors are for and what they are doing, and if you could also explainwhat is going on with your third FOR statement i would appreciate it. Thanks in advance.
no need to use extra for loop.
is this in java
Yes it is in Java, many other languages have some version of split though. Scala and Python have split() that works in the same way, C has str_tok <- apparently works like split
there is a segmentaion fault in your code.
Slightly cleaner and more readable:
can u please explain why n-j-1...
because n will be length and always +1 than index
Can you please explain me
firstDiagonal+=a.at(i).at(i); secondDiagonal+=a.at(count).at(i);
you will get an error. i tested your code and it's showing error
I had no problem running my code when I submitted.
Every "for" has a condition. If you mean no "if" or other explicit condition statements, sure.
that's in int main....not in the function....
this is so wrong answer . O(N^2) is way worse then O(N)
AlissonP, this discussion of inefficiency due to storing useless information actually shouldn't be the focus here, please note that the problem statement says "Given a square matrix of size N x N, calculate the absolute difference between the sums of its diagonals.".
good