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.
Yes, it is a good thinking .. If anyone has read Herbert Schildt or Deitel's Java books would have recognized it..
my solution is the same.. some one else should be able to read it quickly..
static int diagonalDifference(int[][] a) {
int primeDi = 0, secondDi = 0;
// could be improved to
// int sum = 0;
for (int i = 0 , j = a[0].length-1; i < a[0].length ; i++, j--) {
primeDi += a[i][i] ;
secondDi += a[i][j] ;
// could be improved to
// sum = a[i][i] - a[i][j] ;
}
return Math.abs(primeDi - secondDi);
// could be improved to
// return Math.abs(sum);
}
Should not the sum be: sum = sum + (a[i][i] - a[i][j]) I have tried to run like you commented but I got wrong answers. The previous sum needs to be taken into account I think before calculating the new one.
The positions of the elements in a matrix can be seen in terms of i and j and the values of i and j comes out to be as shown in the example below of a 3 x 3 matrix:
0,00,10,21,01,11,22,02,12,2
Here, the 1st digit represents the value of i and the 2nd digit represents value of j. There're two diagonals forming in the matrix given above. If we have to identify the diagonal elements in the matrix given above.
staticintdiagonalDifference(int[][]arr){intx=0;inty=arr[0].Length-1;intsum=0;for(intindex=0;index<arr.Length;index++){//sum -= arr[x][x] - arr[x++][y--]; can also be simplified as below:sum=sum-(arr[x][x]-arr[x++][y--]);}returnMath.Abs(sum);}
Now, with the following test input:
1124456108-12
If we've to look at the approach via position wise:
we've done it as:
We'll try to figure out how loop works on the test-input given above:
We've initialized the value of x to be 0
and the value of y to be arr.Length -1.
Note: arr.Length gives us the number of arrays in the Jagged Array, which in our case is 3.
The Jagged array in question is as follows:
After this operation the value of x++ will give 3 and y-- will give -1.
The value of x and y for next loop operation becomes 3 and -1 respectively and this will fail the loop condition and the loop iteration will stop giving 15 as final result.
iterate forward from the first index in a row and backward from the last index in each row during the same loop iteration. Then add 1 to the forward index position, and subtract 1 from the backward index position on each subsequent iteration until you run out of rows!
All you need is to have an understanding of mathematics and observe the mathematical expression. For example in the diagonal diffrence in a 3X3 array we have the following values for i,j respectively:
0,0 0,1 0,2
1,0 1,1 1,2
2,0 2,2 2,2
so the primary diagonal is 0,0 1,1 2,2 so it is obvious i=j
the secondary diagonal is 2,0 1,1 0,2 so we can easily observe that i+j=n-1 (2+0=3-1, 1+1=2, 0+2=2)
hey pumaboy, try writing out the matrix on paper and mark each box in matrix with row,col coordinates. To get the secondary diagonal, we need the values of [0,2] + [1,1] + [2,0]. Now think about how you would to these coordinates with a for loop. Think about how would you set up your if statements within your loop to capture these values?
public static int diagonalDifference(List> arr) {
// Write your code here
int lastelementindex = arr.size() -1;
int primarydiag = 0;
int secundarydiag = 0;
for (int i=0; i < arr.size(); i++ ){
primarydiag += arr.get(i).get(i);
// reversing array
secundarydiag += arr.get(lastelementindex - i).get(i);
}
The problem explicitly states you start with an NxN array, so, per the rules expressed in the orientation, this would not be an acceptable answer. Not to say it doesn't give the same result, but in a real test, if they are seeing how you handle (a) the problem stated (i.e. changing the problem fundamentally = fail) and (b) how you used the constraints provided to solve the problem, this would be problematic.
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.".
Two nested loops is basic/introductory-level CS knowledge; the outer loop (i) is rows and the inner loop (j) is columns, so each element is located at the appropriate (i,j) location just as it would be in a graphical representation. This should not be "confusing".
Ill explain his approach as mine is the exact same. He first creates the 2 int to hold the sum of each diagonal (d1_v and d2_v), Then during the loop that was precoded to retrieve the lines and set the two dimensional array he is getting the values at each one of those rows that need to be added base on which row (a_i) the loop is on. If you look at my post you will see how this can be utilized without the two dimensional array.
Try writing a matrix in a paper and also give values to i,j,k as given above. You will understand why we need "k" much better that way, than just reading the code.
function diagonalDifference(arr) {
let primDiag = 0
let secDiag = 0
let n = arr.length
for (var i = 0, j = n - 1; i < n; i++, j--) {
primDiag += arr[i][i]
secDiag += arr[i][j]
}
return Math.abs(primDiag - secDiag)
The original poster is not writing a solution in Python, so pointing out functions and constructs available in a completely different language doesn't really add to this particular discussion IMO.
In Python you are able to read and parse whole row easily, but it's not the same in java. The above solution is good for Java. Definitely Python is very powerful language!
The same exact solution is easily accomplished in Java, but it still relies on saving unneeded values to an array which, as has already been pointed out, is actually a less optimal solution because it needlessly stores n^2 - 2n integers in arrays. Java equivalent of this python solution:
public Solution(){
Scanner scan = new Scanner(System.in);
int n = Integer.parseInt(scan.nextLine());
int sumOne = 0;
int sumTwo = 0;
for(int currentOne = 0, currentTwo = n - 1;
currentOne < n;
currentOne ++, currentTwo--
){
String[] inputLine = scan.nextLine().split(" ");
sumOne = sumOne
+ Integer.parseInt(inputLine[currentOne]);
sumTwo = sumTwo
+ Integer.parseInt(inputLine[currentTwo]);
}
System.out.println(Math.abs(sumOne - sumTwo));
}
public static void main(String[] args) {
Solution s = new Solution();
}
I got your point, you are thinking in a very broad perspective applying it in a situation where memory is a constraint. Here it is not! Python takes 0.01 seconds to execute the above program unlike Java(0.1 - 0.29 seconds) that's why I stated it being very powerful. It is good to think in your terms where memory is getting wasted, but not here.
To your point "The same exact solution is easily accomplished in Java, but it still relies on saving unneeded values to an array which, as has already been pointed out, is actually a less optimal solution because it needlessly stores n^2 - 2n integers in arrays." Even in the below solution you are saving every input into curInput n^2 times which contradicts your point.
I'd first like to note that this discussion thread is about a Java solution, and somebody just randomly posted a Python solution in it to demonstrate that the solution could be done without nesting loops (which is not an argument that anyone was making).
Sure, Python is an easy to use and arguably powerful--I never said it wasn't; however, the use of dynamic language magic tends to make things slow, which one of the many reasons Python is generally referred to as a slow language (though improvements have been made over the last 15 years). I'm really not sure what you are using to benchmark but, though Java has a high startup cost, it will almost always execute faster than Python.
As data sets get large, memory is always a constraint; saving n^2 values to an array when only 2n are needed is not a scalable solution.
Please re-read my comment, as I did not contradict my own point at all. Saving a value from an input stream to a single register (which is an optimization any good compiler should make on this code) and then repeatedly overwriting it is not in any way the same as reading the n^2 values as a chunk, breaking the chunk down into n^2 components, storing n^2 values, and reloading and summing the 2n you actually need.
The purpose of my comment was simply to point out that the same solution is accomplishable in Java, because your comment incorrectly stated that Java couldn't read and break up a line the way that Python can and implied that is what makes Python a powerful tool. So I wrote a Java version of the Python poster's code, and pointed out why I still deem it not a good or scalable solution.
It's not quite right to say Java's performance is better than Python or viceversa, as one is better than other in different areas.
I would like to repeat the following things again -
It is good to think in your terms where memory is getting wasted, but "not here". I am a game developer and believe me I know exactly when one should be worrying about memory.
I agree to the point of yours that saving a value into a single register is better than reading n^2 values as a chunk. But, is it arguably bad? Though we have better readability, and also it is easy to code. Again, believe me it is not!
Sorry, I came 3 years later. Buy I want to poin out that the problem ask for a function that take an array.
Touching anything in main is contrary to the excercise spirit. The program have an array in some place. The excercise main is there to make a mashed input and to test the answer. In python are better solutions to test a function ( or a class or a completet lib by the way) but this is the aproach used here.
So, you can do something in the line you do. For example you can make it whit iterators that take care of reading the file until needed and storing only the numbers you need and consuming them, that would be an interesting answer, but not what the problem is about.
I like it. It was similar to mine in that there isn't a nested for loop iterating over multi dimensional array. My solution is unfortunately more pedantic and incurs looping twice.
Great approach! Just a quick comment. You can take differences of left and right terms as you import each row. This computes a cumulative difference. There is no need to compute the sums first and then take differences. It's a bit simpler and, hopefully, faster ;)
This is a solution where we go through the matrix only once, no arrays just check if we add the number to one of the diagonals or both.
publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);intN=in.nextInt();intsumA=0,sumB=0;intM=N*N;//counter for first diagonalintcountA=N-N;// 0 -> N*N ; step N+1 // counte for second diagonalintcountB=N-1;// N-1 -> N*N-N; step N-1 intcountBLimit=M-1;// the last element is not for this diagonal for(inti=0;i<M;i++){intk=in.nextInt();if(i==countA){sumA+=k;countA+=N+1;}if(i==countB&&countB<countBLimit){sumB+=k;countB+=N-1;}}System.out.println(Math.abs(sumA-sumB));}
Well, he doesn't. Actually he does not care about "matrixes"(vectors of vectors), he simply looks in each simple vector by time, and pick two values (he already knows what values to pick, no verifying is needed), without relating one vector to another in a major matrix. Capisce?
The brightness about this solution is that you don't have to verify each cell of the matrix to know if it is the value you need, cause you already know what cells to pick:
1 row: first and last;
2 row: second and last but one;
3 row: third and last but two;
You are not paying attention to what input().split(" ") does. Yes string manipulation library could be highly optimzed that he might be saving some CPU cycles but I'm not sure if string tokenization is constant time operation. Definitely a cleaner and better solution though.
Great work rick.thanks for the idea of not using an array.....being a beginner all will think of using arrays which unnecessarilly will occupy some storage space.thanks once again for adding this code..
//I did it this way with one loop, but mine is less effective
for(i=0;i<n*n;i++)
{
cin>>t;
if(i%n==(i/n)%n){Lsum+=t;}
if(i%n==n-1-(i/n)%n){Rsum+=t;}
}
cout<<abs(Lsum-Rsum);
Though it's a single loop, still it's n*n loop. But that's a great formulae you have come up with, lot of thought process! But again I have read some where that modulos operation is very costly and try to avoid it. Thanks for sharing the solution.
It's reading in a value from cin and assigning it to a previously declared variable named curInput. Each time the loop runs, it reads a variable value, assigns it to curInput, processes it accordingly, and then loops again until the loop is finished. Because the value of curInput is processed inside the loop and not needed again after processing, the value of curInput just gets overwritten at each cin >> curInput;.
You are correct in that it is also the bitshift operator. C and C++ also use them as IO operators with cin and cout. my understanding as far as the reason for it is that they wanted to make the IO operators analagous to unix IO redirection operators.
Many people think that operator overloading reduces the comprehensibility of code. Perhaps for this reason, the designers of Java decided against allowing operators to be re-defined. (Even so, Java natively overloads the "+" operator for java.lang.String to concatenate rather than perform a mathematical operation.)
I have a question regarding this condition
If our numInputs is an odd number
if(j == k)
{
leftD += curInput;
}
at some point we will have a (j==k) in rightD as well
and at this point the code will add to the leftD and rightD as well which would make the same to give you a wrong answer. Wont It?
Please forgive me. Noob Question if i havent seen something correctly.
Because the numInputs is an odd number, the two diagonals will always cross at some point, resulting in one cell that is part of the sum of both diagonals. For a 3x3 matrix, the two diagonals are {(3,1), (2,2), (1,3)} and {(1,1), (2,2), (3,3)}; (2,2) is the center point and is part of both diagonals.
it took me several minutes to understand your code im not that fast to analyse problems, what surprise me is how you decomposed the issue and found a solution within the loop, could you give me some tips about organize thoughts and everything to perform a better logic and not hardcoding things just like my solutions XD. thanks
Thx, dude! Nice approach! I did it before using array to store a literal matrix, but after reading it and the comments bellow, y'all convinced me to make it without storing data into arrays. Doing this way was a bit challenging using python, cause im not quite acquainted with the language, yet. But it worked. Thx!
And yes, it's better not to store data in arrays if you won't use it later.
Ah, your "(j+k == (numInputs-1)" condition is very nice. I was using "j == (numInputs-1)-k and k == (numInputs-1)-j". Your logical solution for this condition is much better than mine. Thanks for this learning too.
It is reading input from a variable curInput. cin is the keyword of reading inputs in c++. >> is the operator to read values.
Similarly cout<< curInput prints the output.
Same here. Except since we are calculating the difference, I merely declared an int of 0 to hold the difference. In the first if conditional analogous to yours, I added to this int. In the second conditional, I subtracted from this int. My logic was, these early subtractions help keep the numbers small preventing early overflows.
Oh nice, I did this too in Javascript! I was afraid it wouldn't work because the pattern "seemed" to be that the x/y coordinates added up to be 1 less than N.
var backSlash = 0;
var forwardSlash = 0;
for (var i = 0; i < n; i++) {
for (var j = 0; j < n; j++) {
if (i == j) {
backSlash += a[i][j];
}
if (i + j == n-1) {
forwardSlash += a[i][j];
}
}
}
console.log(Math.abs(backSlash - forwardSlash));
We can reduce the complexity by both loop at same time execute and no if condition like this:
i think its better approach instead of using two if condition.
for(int i = 0,j = n; i < n && j > 0; i++,j--){
diag1 += arr[i][i];
diag2 += arr[i][j];
}
Could you maybe explain the:
"cin >> curInput;"?
I know that >> is used for bitshifting, but that is about it.
Eveen after research I still have no coue how your solution works.
It is simple. The value of j and k is the left diagonal for a square matrix is always eaqual whereas for the right digonal, the sum of j and k is equal to the number of rows/column int the matrix.
Two for loops expensive..
function solve(n, arr){
var primarySum = 0;
var secondarySum = 0;
arr.forEach(function(v, row){
primarySum+=v[row];
secondarySum+=v[n-row-1];
});
Explain j+k == (numInputs-1) ??
For every matrix element ajk. When j+k would be equal to numInputs+1, then and only then it is right Diagonal. For example, in matrix of three, every element with j+k=4 (where 4 is numInput 3 + 1). Kindly explain this to me.
Mine followed a similar logic, but you don't actually have to use two for loops.
You already know the relationship between j and k, so you can use just one for loop to increment j.
defdiagonalDifference(arr)# Write your code hereprimary=arr.map.with_index{|line,i|line[i]}.sumsecondary=arr.map.with_index{|line,i|line[-i.next]}.sumreturn(primary-secondary).absend
Any Kotlin guys here? I'm trying to use the same logic here, but seems like always getting Runtime Error all the time. Could somebody tell me what is wrong here?
Diagonal Difference
You are viewing a single comment's thread. Return to all comments →
I went for a non-array approach. Feedback much appreciated :)
Interesting! (j+k == (numInputs-1)) is cool.
Yah Really interesting
include
include
include
include
include
include
include
include
include
int main() { int a[100][100],n,c=0,d=0,i,j,sum=0; scanf("%d",&n); for(i=0;i for(i=0;i
int main() { int a[100][100],n,c=0,d=0,i,j,sum=0; scanf("%d",&n); for(i=0;i for(i=0;i
haha lol
kya karti rhte ha vellii
hat bosdiko
u dont need two loops for this, in one itself it can be done
how???
I still have one extra variable, which is unnecessary
What happen if input values are changed. I mean couple of more negative values in matrix
Does not affect the outcome, since it is the difference we are after, it is always a positive value
can be done in ((n-1)/2)+1 iteration
For a more readable format:
Cannot read this. always go for a solutions others can read
could you explain?
Very good love you
Hey hi man just wanted to know how do you find time complexity because for me i got exceeded time limit
just in case you didnt know the for loop couldve been written like this for a cleaner look
or as
Great
Yes, it is a good thinking .. If anyone has read Herbert Schildt or Deitel's Java books would have recognized it.. my solution is the same.. some one else should be able to read it quickly..
This comment has helped me understand not only the solution, but how to get to the solution. From a rookie programmer, thank you for the insight!
this is awesome thanks
Should not the sum be: sum = sum + (a[i][i] - a[i][j]) I have tried to run like you commented but I got wrong answers. The previous sum needs to be taken into account I think before calculating the new one.
This is more efficient:
n--; for(int i = 0; i <= n; i++){ sum1 += a[i][i]; sum2 += a[n-i][i]; }
Like this is more efficient:
I think this is the most elegant a clear solution. Well done
This is a fantastic solution.
Beautiful code
exact same approach!
Complexity O(N). One Loop.
You will have to change to solution += a[row][row] - a[row++][column--];
Did you try it?
doesn't matter , its abs diff
Hi there,
This solution seems to work beautifully, however I'm a little lost as to how. Any chance you could provide a little runthrough?
Many thanks, M
The positions of the elements in a matrix can be seen in terms of i and j and the values of i and j comes out to be as shown in the example below of a 3 x 3 matrix:
Here, the 1st digit represents the value of i and the 2nd digit represents value of j. There're two diagonals forming in the matrix given above. If we have to identify the diagonal elements in the matrix given above.
Since the square matrix in the question/problem is represented by a Jagged Array (array of arrays). If you don't have an idea of what Jagged Array is, then you might need to first know about the Jagged Array at the following link: https://docs.microsoft.com/en-us/dotnet/csharp/programming-guide/arrays/jagged-arrays
Now we analyse the solution:
The solution is as follows:
Now, with the following test input:
If we've to look at the approach via position wise: we've done it as:
We'll try to figure out how loop works on the test-input given above: We've initialized the value of x to be 0 and the value of y to be arr.Length -1. Note: arr.Length gives us the number of arrays in the Jagged Array, which in our case is 3. The Jagged array in question is as follows:
So the size of Jagged Array: arr in question is 3 (which is arr.Length) where each array further contains a simple array of int as can be seen above.
Now let's analyse how loop works:
1st round of loop will run as follows:
After this operation the value of x++ will give 1 and y-- will give 1. The value of x and y for next loop operation becomes 1 and 1 respectively.
2nd round of loop will run as follows:
After this operation the value of x++ will give 2 and y-- will give 0. The value of x and y for next loop operation becomes 2 and 0 respectively.
3rd round of loop will run as follows:
After this operation the value of x++ will give 3 and y-- will give -1. The value of x and y for next loop operation becomes 3 and -1 respectively and this will fail the loop condition and the loop iteration will stop giving 15 as final result.
Thank you very much for your explanation!
My solution was similar but not as elegant. Nice work.
iterate forward from the first index in a row and backward from the last index in each row during the same loop iteration. Then add 1 to the forward index position, and subtract 1 from the backward index position on each subsequent iteration until you run out of rows!
def diagonalDifference(arr): diag1 = 0 diag2 = 0 i1 = 0 i2 = len(arr)-1 for i in range(len(arr)): diag1 += arr[i1][i1] diag2 += arr[i1][i2] i1 += 1 i2 -=1 return abs(diag1 - diag2)
lol why did u got dislikes
wow thats creative!
me too got the same logic
same here (Y)
Yeah i never could have thought of that!!
How did you came up with the equation? I mean I'm new to programming and I need tips.
All you need is to have an understanding of mathematics and observe the mathematical expression. For example in the diagonal diffrence in a 3X3 array we have the following values for i,j respectively:
0,0 0,1 0,2
1,0 1,1 1,2
2,0 2,2 2,2
so the primary diagonal is 0,0 1,1 2,2 so it is obvious i=j the secondary diagonal is 2,0 1,1 0,2 so we can easily observe that i+j=n-1 (2+0=3-1, 1+1=2, 0+2=2)
nothing explained is obvious or as clear as could be.
I agree entirely. This was not a clear solution but clean code. Very confusing to a new coder.
nice solution
It's nothing sort of cool.
The main approach uses (i == n-j-1) in this approach he is simply taking j from the right and putting it on the left side of the ==
i == n-j-1 is as same as i + j == n-1
yeah
me too same approch...
Same, though my second if statement was the mathematically equivalent (i == (numInputs - j -1)).
i=numinputs-j+1
i didn't understand the above logic..help me out
hey pumaboy, try writing out the matrix on paper and mark each box in matrix with row,col coordinates. To get the secondary diagonal, we need the values of [0,2] + [1,1] + [2,0]. Now think about how you would to these coordinates with a for loop. Think about how would you set up your if statements within your loop to capture these values?
public static int diagonalDifference(List> arr) { // Write your code here int lastelementindex = arr.size() -1; int primarydiag = 0; int secundarydiag = 0; for (int i=0; i < arr.size(); i++ ){ primarydiag += arr.get(i).get(i); // reversing array secundarydiag += arr.get(lastelementindex - i).get(i); }
Yeah. You don't need to save the matrix into an array
good
The problem explicitly states you start with an NxN array, so, per the rules expressed in the orientation, this would not be an acceptable answer. Not to say it doesn't give the same result, but in a real test, if they are seeing how you handle (a) the problem stated (i.e. changing the problem fundamentally = fail) and (b) how you used the constraints provided to solve the problem, this would be problematic.
I love this solution, neat and easy to understand... though for a beginner like me, array is our first choice. Thanks for sharing by the way.
super
Unfortunately, while clever, it doesn't actually address the problem as given, which starts with the requirement of an NxN array.
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
cool :) am noob coder! wasted 40 mins for this logic but finally happy.
You are not wasting any time when you are coding. You will always learn something if it takes sometime and you finish it. :)
absolutely right.....
explain this to facebook co-founders. They actually learnt how to feel cheated by the better croook.
same!
I performed similar logic on each row, but used a temporary array. Difference being one loop absent confusing for-loop nesting. Solution in C#.NET.
Two nested loops is basic/introductory-level CS knowledge; the outer loop (i) is rows and the inner loop (j) is columns, so each element is located at the appropriate (i,j) location just as it would be in a graphical representation. This should not be "confusing".
I did the Math on the reading loop:
Hey there could you add an explanation as to what your code does, i would appreciate it. Thanks in advance.
Ill explain his approach as mine is the exact same. He first creates the 2 int to hold the sum of each diagonal (d1_v and d2_v), Then during the loop that was precoded to retrieve the lines and set the two dimensional array he is getting the values at each one of those rows that need to be added base on which row (a_i) the loop is on. If you look at my post you will see how this can be utilized without the two dimensional array.
Nice work dude...!!
did the same in c but i didnt get the output
I used this as a basis for my c# submission as I was quite stumped.
good thinking
Really nice one.
You can actually move up the k -= 1 into the outer loop next to the i++ as:
Yes, thanks!
what's the use of k here?? k=size-1...and k-- ? can Anyone help out..please
Try writing a matrix in a paper and also give values to i,j,k as given above. You will understand why we need "k" much better that way, than just reading the code.
yes I dont get k? i reprents rows,j represents columns i think but k?
well you can use i in place of k that's not a problem that's just a variable used for looping
Here is the video explaination- https://youtu.be/f6bTIsj9ne8
good
Nice. You can remove the conditional though, and complete this in one loop. Here is my solution in JavaScript.
Hello lemuel,
Can you please explain more to me about this????
I altered a little.
}
super!! logic
Nice logic :)
there's no need for nested for loops:
The original poster is not writing a solution in Python, so pointing out functions and constructs available in a completely different language doesn't really add to this particular discussion IMO.
Well, it added to me.
@allison it is all about algorithmic appraoch. A person can use any language to exhibit his/her ideas IMO.
In Python you are able to read and parse whole row easily, but it's not the same in java. The above solution is good for Java. Definitely Python is very powerful language!
The same exact solution is easily accomplished in Java, but it still relies on saving unneeded values to an array which, as has already been pointed out, is actually a less optimal solution because it needlessly stores n^2 - 2n integers in arrays. Java equivalent of this python solution:
I got your point, you are thinking in a very broad perspective applying it in a situation where memory is a constraint. Here it is not! Python takes 0.01 seconds to execute the above program unlike Java(0.1 - 0.29 seconds) that's why I stated it being very powerful. It is good to think in your terms where memory is getting wasted, but not here.
To your point "The same exact solution is easily accomplished in Java, but it still relies on saving unneeded values to an array which, as has already been pointed out, is actually a less optimal solution because it needlessly stores n^2 - 2n integers in arrays." Even in the below solution you are saving every input into curInput n^2 times which contradicts your point.
Yours Java equivalent solution to Python looks so hard to read.
Look at this Python solution:
Simple and Powerful!
We need to learn and understand the balance required between performance and memory usage.
I'd first like to note that this discussion thread is about a Java solution, and somebody just randomly posted a Python solution in it to demonstrate that the solution could be done without nesting loops (which is not an argument that anyone was making).
It's not quite right to say Java's performance is better than Python or viceversa, as one is better than other in different areas. I would like to repeat the following things again -
Sorry, I came 3 years later. Buy I want to poin out that the problem ask for a function that take an array.
Touching anything in main is contrary to the excercise spirit. The program have an array in some place. The excercise main is there to make a mashed input and to test the answer. In python are better solutions to test a function ( or a class or a completet lib by the way) but this is the aproach used here.
So, you can do something in the line you do. For example you can make it whit iterators that take care of reading the file until needed and storing only the numbers you need and consuming them, that would be an interesting answer, but not what the problem is about.
neither my code , nor yours is printing, please point the error
try this
Here is a python 3 version below:
plz explain
Actually the above solution was not working for me, so I did the solution without taking the input as it was already described in the main function.
Awesome bro. U keep it simple
n is not defined inside this function . then how can you use n inside this fun
hi i am a beginner in python can anyone explain me , how have they input 2D list in Python from the user ....
for a_i in range(n): a_t = [int(a_temp) for a_temp in input().strip().split(' ')] a.append(a_t)
That python code was brilliant
hi Allison, below is my solution. Can you please provide your feedback.
I like it. It was similar to mine in that there isn't a nested for loop iterating over multi dimensional array. My solution is unfortunately more pedantic and incurs looping twice.
very elegant solution, mine was similar:
You are great
Great approach! Just a quick comment. You can take differences of left and right terms as you import each row. This computes a cumulative difference. There is no need to compute the sums first and then take differences. It's a bit simpler and, hopefully, faster ;)
since i am a beginner will you please tell me what is the function of .split ?
Let's say you have "1,2,3,hello" and you call .split(","). This will give you back an array of ["1", "2", "3", "hello"].
This is a solution where we go through the matrix only once, no arrays just check if we add the number to one of the diagonals or both.
Thnx a lot
what is the need to parse the value to integer?
There is no performance improvement in unfolding the 2d matrix in to 1d. Thats what you did here.
Well, he doesn't. Actually he does not care about "matrixes"(vectors of vectors), he simply looks in each simple vector by time, and pick two values (he already knows what values to pick, no verifying is needed), without relating one vector to another in a major matrix. Capisce?
It is a clever solution, dude!
The brightness about this solution is that you don't have to verify each cell of the matrix to know if it is the value you need, cause you already know what cells to pick:
1 row: first and last; 2 row: second and last but one; 3 row: third and last but two;
and so on..
Clever!
You are not paying attention to what input().split(" ") does. Yes string manipulation library could be highly optimzed that he might be saving some CPU cycles but I'm not sure if string tokenization is constant time operation. Definitely a cleaner and better solution though.
It can be as simple as a line:
print(abs(sum([a[i][i] - a[i][n-i-1] for i in range(n)])))
the square brackets around the difference/range part of the statement are not necessary.
Little bit tweaked example from above:
input().split() gives error
EOFError: EOF when reading a line
This is great. I don't understand it much though... can anyone help?
Thanks a lot!!
one liner python
other approach
Similair code
Great work rick.thanks for the idea of not using an array.....being a beginner all will think of using arrays which unnecessarilly will occupy some storage space.thanks once again for adding this code..
Though it's a single loop, still it's n*n loop. But that's a great formulae you have come up with, lot of thought process! But again I have read some where that modulos operation is very costly and try to avoid it. Thanks for sharing the solution.
Could someone help me understand what's happening with the line "cin >> curInput;"?
It's reading in a value from
cinand assigning it to a previously declared variable namedcurInput. Each time the loop runs, it reads a variable value, assigns it tocurInput, processes it accordingly, and then loops again until the loop is finished. Because the value ofcurInputis processed inside the loop and not needed again after processing, the value ofcurInputjust gets overwritten at eachcin >> curInput;.Ok, so it's not bitshifting? I thought the >> operator was for right bitshift, which is why I was so confused.
You are correct in that it is also the bitshift operator. C and C++ also use them as IO operators with cin and cout. my understanding as far as the reason for it is that they wanted to make the IO operators analagous to unix IO redirection operators.
Just a small aside - these IO operators were introduced in C++ - they don't exist in C.
Yes, C++ allows classes to redefine the basic operators for their own purposes. This feature is usually referred to as "operator overloading": https://isocpp.org/wiki/faq/operator-overloading#op-ov-benefits
So, the handling of ">>" when used with the istream class is customized for each possible argument type: http://www.cplusplus.com/reference/istream/basic_istream/operator%3E%3E/
Many people think that operator overloading reduces the comprehensibility of code. Perhaps for this reason, the designers of Java decided against allowing operators to be re-defined. (Even so, Java natively overloads the "+" operator for java.lang.String to concatenate rather than perform a mathematical operation.)
sorry but i did not understand this properly. Can you explain it clearly please? Thank you in advance.
awesome
Hi,
I have a question regarding this condition If our numInputs is an odd number
if(j == k) { leftD += curInput; }
at some point we will have a (j==k) in rightD as well and at this point the code will add to the leftD and rightD as well which would make the same to give you a wrong answer. Wont It?
Please forgive me. Noob Question if i havent seen something correctly.
Because the numInputs is an odd number, the two diagonals will always cross at some point, resulting in one cell that is part of the sum of both diagonals. For a 3x3 matrix, the two diagonals are {(3,1), (2,2), (1,3)} and {(1,1), (2,2), (3,3)}; (2,2) is the center point and is part of both diagonals.
it took me several minutes to understand your code im not that fast to analyse problems, what surprise me is how you decomposed the issue and found a solution within the loop, could you give me some tips about organize thoughts and everything to perform a better logic and not hardcoding things just like my solutions XD. thanks
whats about the number which is common in both digonal....
I don't even bother storing leftD and rightD.
Looks cool, but I don't like using bools for their binary values.
#!/bin/bash
read n;
sum=0;
for i in n ); do
read line;
sum=sum +
echoi -d " "- (echo((i )) -d " ") ))done
echo $sum | sed -e 's/-//'`
Thx, dude! Nice approach! I did it before using array to store a literal matrix, but after reading it and the comments bellow, y'all convinced me to make it without storing data into arrays. Doing this way was a bit challenging using python, cause im not quite acquainted with the language, yet. But it worked. Thx!
And yes, it's better not to store data in arrays if you won't use it later.
Ah, your "(j+k == (numInputs-1)" condition is very nice. I was using "j == (numInputs-1)-k and k == (numInputs-1)-j". Your logical solution for this condition is much better than mine. Thanks for this learning too.
Watch this:
print(abs(sum([a[i][i] - a[i][n-i-1] for i in range(n)])))
Can someone explain what this line does?:
It is reading input from a variable curInput. cin is the keyword of reading inputs in c++. >> is the operator to read values. Similarly cout<< curInput prints the output.
A very clean solution, thank's for share ur algorithm ;)
Cool!
I did something similar. :)
}
its not working for me
Super cool yar!!
Why complexity of nested loop? This is how I solved it:
long sum1 = 0; long sum2 = 0;
This is what I did too! Takes O(n) time. Cheers!
Did the same in Java [ O(n) time complexity ]:
why did keep + symbols infroont of sum1 and sum2..?
its like SUM=SUM+arr[i][i];
The + indicated that ^
Amazing Man!! The solution is just AMAZING !!
I like this idea. I see that you don't need O(n^2) storage space but does it need O(n^2) time complexity? If so, can it be reduced?
Nice!
really cool approach
It means you are just considering the input values when the if conditions are true, otherwise all other values are discarded. Right ?
Thats Perfect !!
superb sir hats off.......
nicely done
Same here. Except since we are calculating the difference, I merely declared an int of 0 to hold the difference. In the first if conditional analogous to yours, I added to this int. In the second conditional, I subtracted from this int. My logic was, these early subtractions help keep the numbers small preventing early overflows.
This one is so cool and clear, thanks for sharing.
public static int arraySum(int[][] array){ int total = 0;
}
Nice approach
You are using 2 variables "left and rigth" when you can use only one. wich one should be incremented and decremented.
Second loop (k) is not needed, index can be caluculated from array dimension and j
this logic (j+k==n-1)is short and precise
nice one!
Oh nice, I did this too in Javascript! I was afraid it wouldn't work because the pattern "seemed" to be that the x/y coordinates added up to be 1 less than N.
What is the curInput used for?
The current input :) cin >>> curInput.
wow, awesome man you showed me a whole new way to look at this problem.
now it's look like a algorithm domain...
cool..bro
it is the best solution of the question given and it is good even for large value of N;
I did about the same, but using a single for loop and a single sum variable:
thanks
nice approch , solution is quite good
Cool !!!
it was my condition for show an different example
We can reduce the complexity by both loop at same time execute and no if condition like this:
this won't work for an odd square matrix like 3x3, 5x5, 7x7
Could you maybe explain the: "cin >> curInput;"? I know that >> is used for bitshifting, but that is about it. Eveen after research I still have no coue how your solution works.
Thanks in advance.
See https://www.hackerrank.com/challenges/diagonal-difference/forum/comments/92219
Thank you very much for the quick reply :)
Very intersting solution.
i tried with this method but it is showing terminated due to timeout
Great Dude! if(j+k == (numInputs-1))
really instresting logic. how you find this?
It is simple. The value of j and k is the left diagonal for a square matrix is always eaqual whereas for the right digonal, the sum of j and k is equal to the number of rows/column int the matrix.
How can I use like this code in Java
Sorry I'm a beginner haha
Great !!
great thinking :D
Interesting !!
sorry but i did not understand the "cin >> curInput" line :(
awesome bro !!
Haha without using array approach is very cool.
Brilliant!
what would be the numInputs here, example plz.
please explain it.
Cool answer! I couldn't figure out until i draw the total of x and y coordinate in paper. Total of right diagonal is always same!
Two for loops expensive.. function solve(n, arr){ var primarySum = 0; var secondarySum = 0; arr.forEach(function(v, row){ primarySum+=v[row]; secondarySum+=v[n-row-1]; });
return Math.abs(primarySum - secondarySum); }
What does this do? If this is a bit shift, what is the purpose?
if(j+k == (numInputs-1)) You are awesome :)
include
include
include
include
include
include
include
include
include
int main() { int a[100][100],n,c=0,d=0,i,j,sum=0; scanf("%d",&n); for(i=0;i for(i=0;i
you are good in math,certainly!
second=0; n-1; for(i<i++){ a[i]; a[j]; $j--; }
wow.. surely a thing to learn
nice approach!
that is more nicer way than the way i did it k == (size-1)-j
awesome logic dude
Awful solution, it takes O(n^2) which is quadratic time, this does not scale. No idea why people are cheering this code.
Awesome!
It's Simply so brilliant!!!
Aren't nested for loops a performance bottleneck? They perscribe to O(n^2) right? Isn't that unscalable?
why is there (numinputs-1) and not (numinputs+1)?
Explain j+k == (numInputs-1) ?? For every matrix element ajk. When j+k would be equal to numInputs+1, then and only then it is right Diagonal. For example, in matrix of three, every element with j+k=4 (where 4 is numInput 3 + 1). Kindly explain this to me.
a11 b12 c21 c22
Here 1+2 and 2+1 = 3.
Did this in python
Wow that makes my version of this super dirty in comparison.
Mine followed a similar logic, but you don't actually have to use two for loops. You already know the relationship between j and k, so you can use just one for loop to increment j.
Came to the same result, but ruby way. Just one loop
Crazy! I got the EXACT same. Important to note you have to pass
nto the function.N can be deduced from Array size I wrote this :
O(N)Solution -
l=0 p=0 for i in range(len(a)): l+= a[i][i] p+= a[i][len(a)-1-i]
print(abs(l-p))
dang.... what.. is curInput, and cin and leftD, as I finished by myself I was very proud but realized, i dont know anything lol
Any Kotlin guys here? I'm trying to use the same logic here, but seems like always getting Runtime Error all the time. Could somebody tell me what is wrong here?
Nice, this is a rigth algorithm.
static int diagonalDifference(int[][] a) { int l=a.length; int d1=0; int d2=0; for(int i=0;i