djgarrick I went for a non-array approach. Feedback much appreciated :)
for(int j = 0; j < numInputs; j++){ for(int k = 0; k < numInputs; k++){ cin >> curInput; if(j == k){ leftD += curInput; } if(j+k == (numInputs-1)){ rightD += curInput; } } } ans = abs(leftD-rightD);
dhananjay77 Interesting! (j+k == (numInputs-1)) is cool.
Waqas1 Yah Really interesting
CHODHARY 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
CHODHARY 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
tarunapal9582 haha lol
mukul131999 kya karti rhte ha vellii
CHODHARY hat bosdiko
Zaf_Mohamed u dont need two loops for this, in one itself it can be done
fayazeleena how???
ishwor I still have one extra variable, which is unnecessary
static void Main(String[] args) { int n = Convert.ToInt32(Console.ReadLine()); int[][] a = new int[n][]; for(int a_i = 0; a_i < n; a_i++){ string[] a_temp = Console.ReadLine().Split(' '); a[a_i] = Array.ConvertAll(a_temp,Int32.Parse); } int totalSum=0; int j=n-1; for(int i=0;i<n;i++){ totalSum=a[i][i]-a[j][i]+totalSum; j--; } Console.WriteLine(Math.Abs(totalSum)); }
[DELETED] [deleted]rautnilesh8 What happen if input values are changed. I mean couple of more negative values in matrix
max_ragmo Does not affect the outcome, since it is the difference we are after, it is always a positive value
garg_gourav can be done in ((n-1)/2)+1 iteration
for (int i = 0; i < ((n - 1) / 2) + 1; i++) { total = ar[i][i] - ar[i][n - 1 - i] + ((i != n - 1 - i) ? ar[n - 1 - i][n - 1 - i] - ar[n - 1 - i][i] : 0) + total; }
kps_forums For a more readable format:
int squareDiffHalf(vector<vector<int>> matrix, int n) { int diff = 0; for (int i = 0; i < n/2; i++) { diff += (matrix[i][i] + matrix[n-i-1][n-i-1] - matrix[i][n-i-1] - matrix[n-i-1][i]); } return abs(diff); }
neostarteon Cannot read this. always go for a solutions others can read
mohan_krish_dk_1 could you explain?
A_Band Very good love you
dkarthicks27 Hey hi man just wanted to know how do you find time complexity because for me i got exceeded time limit
gragest just in case you didnt know the for loop couldve been written like this for a cleaner look
for(int i = 0, j = n-1; i < n; i++, j--){ sum1 += a[i][i]; sum2 += a[j][i]; }
or as
for(int i = 0; i < n; i++){ sum1 += a[i][i]; sum2 += a[(n-1)-i][i]; }
nikhilraynade Great
niyaziozturkg 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); }mjperry94 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!
muhammed_saafan this is awesome thanks
maksad_annamurad 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.
josesalvador_pe1 This is more efficient:
n--; for(int i = 0; i <= n; i++){ sum1 += a[i][i]; sum2 += a[n-i][i]; }
josesalvador_pe1 Like this is more efficient:
n--;
for(int i = 0; i <= n; i++){
sum1 += a[i][i]; sum2 += a[n-i][i];}
rlynjb [deleted]adityash_721 impressive sol. dude
imran_nazir I think this is the most elegant a clear solution. Well done
micahbales This is a fantastic solution.
JuandiM Beautiful code
societalghost Nice :)
s1996vintage exact same approach!
bit_tracer Complexity O(N). One Loop.
static int diagonalDifference(int[][] a) { int row=0; int column=a[0].length - 1; int solution = 0; for(int index=0;index<a.length;index++){ solution -= a[row][row] - a[row++][column--]; } return Math.abs(solution); }
anishpaul92 You will have to change to solution += a[row][row] - a[row++][column--];
bit_tracer Did you try it?
gillupenn doesn't matter , its abs diff
maxwell_robson 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
mihir_bell [deleted]
rubbal_bhusri13 [deleted]rubbal_bhusri13 [deleted]rubbal_bhusri13 [deleted]rubbal_bhusri13 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,0 0,1 0,2 1,0 1,1 1,2 2,0 2,1 2,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.
1st diagonal: 0,0 ; 1,1 ; 2,2. 2nd diagonal: 2,0 ; 1,1 ; 0,2.
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:
static int diagonalDifference(int[][] arr) { int x = 0; int y = arr[0].Length - 1; int sum = 0; for(int index=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--] ); } return Math.Abs(sum); }
Now, with the following test input:
11 2 4 4 5 6 10 8 -12
If we've to look at the approach via position wise: we've done it as:
Taking sum = 0 sum = sum - (position(0,0) - position(0,2)) then sum = sum - (position(1,1) - position(1,1)) then sum = sum - (position(2,2) - position(2,0))
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:
int[][] arr = new int[3][]; arr[0] = new int[] {11, 2, 4}; arr[1] = new int[] {4, 5, 6}; arr[2] = new int[] {10, 8, -12};
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:
the value of x = 0; the value of y = 2; //came from arr.Length - 1 i.e. 3 - 1 = 2 arr[x][x] = arr[0][0] = 11 arr[x++][y--] = arr[0][2] = 4 sum = sum - (arr[x][x] - arr[x++][y--]) sum = sum - (arr[0][0] - arr[0][2]) sum= 0- (11-4) sum = -7
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:
the value of x = 1 the value of y = 1 arr[x][x] = arr[1][1] = 5 arr[x++][y--] = arr[1][1] = 5 sum = sum - (arr[x][x] - arr[x++][y--]) sum = sum - (arr[1][1] - arr[1][1]) sum= -7 -(5 - 5) sum = -7
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:
the value of x = 2 the value of y = 0 arr[x][x] = arr[2][2] = -12 arr[x++][y--] = arr[2][0] = 10 sum = sum - (arr[x][x] - arr[x++][y--]) sum = sum - (arr[2][2] - arr[2][0]) sum = -7 -(-12 - 10) sum = - 7 -(-22) sum = -7 + 22 sum = 15
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.
jacobkalas Thank you very much for your explanation!
williammcdonald1 My solution was similar but not as elegant. Nice work.
jk_cahill 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!
albrecht_scott [deleted]stevefrazee123 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)
lianyuu one loop
int diagonalDifference(vector<vector<int>> arr) { int sum1 = 0; int sum2 = 0; int j = arr.size()-1; for(int i = 0; i < arr.size(); i++){ sum1 += arr[i][i]; sum2 += arr[i][j]; j--; } return abs(sum1-sum2);
} `
sunil1463 [deleted]osama119786 lol why did u got dislikes
larenmark wow thats creative!
calgspv me too got the same logic
mohmmd_shoaib same here (Y)
Rjt5412 Yeah i never could have thought of that!!
pawin3210 How did you came up with the equation? I mean I'm new to programming and I need tips.
ckastam 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)
rob_matthews nothing explained is obvious or as clear as could be.
tyler_elit I agree entirely. This was not a clear solution but clean code. Very confusing to a new coder.
amadoundongothi1 nice solution
ggllgg [deleted]
saryan573 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
king2701 yeah
DEEPAKRODA7 def diagonalDifference(arr,n): left,right,i=0,0,0 while i != n: left+=arr[i][i] right+=arr[i][n-1-i] i+=1 return abs(left-right)
nazarstakhovskyi [deleted]
nyesil that is genius.
rebelgiri me too same approch...
AllisonP Same, though my second if statement was the mathematically equivalent (i == (numInputs - j -1)).
amrita9 i=numinputs-j+1
pumaboy_naik i didn't understand the above logic..help me out
xslipstream 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?
socio_17 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); }
return Math.abs(primarydiag-secundarydiag); }
isurudaulagala Yeah. You don't need to save the matrix into an array
santhosh_sunkari good
Turings_Ghost 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.
ekahjhake 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.
pragu super
Turings_Ghost Unfortunately, while clever, it doesn't actually address the problem as given, which starts with the requirement of an NxN array.
Arvindcr7 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.
AllisonP 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).
airais 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.
AllisonP 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.
irvision_bsb 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.
GaborBartal 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.
ichidan 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.
class Solution : public ISolution { private: int evaluate(const std::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.
Just my two cents.
GaborBartal 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.
Tritonal 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.
AllisonP 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).
haideragha 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.
AllisonP 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.
drew_adorno You do not need to have any conditions to complete this problem.
int main() { int n; int firstDiagonal=0; int secondDiagonal=0; cin >> n; int count=n-1; vector< vector<int> > a(n,vector<int>(n)); for(int a_i = 0;a_i < n;a_i++){ for(int a_j = 0;a_j < n;a_j++){ cin >> a[a_i][a_j]; } } for(int i=0; i<n; i++) { firstDiagonal+=a.at(i).at(i); secondDiagonal+=a.at(count).at(i); count--; } cout << abs(firstDiagnol-secondDiagnol); return 0; }Because the diagonal are always going to be positions we know when we have the size of the matrix.
thriggle 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));wei972008 [deleted]JocoMagic 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.
Puneet3821 no need to use extra for loop.
for(int a_i = 0;a_i < n;a_i++){ for(int a_j = 0;a_j < n;a_j++){ cin >> a[a_i][a_j]; } d1 = d1 + a[a_i][a_i]; d2 = d2 + a[a_i][n-1-a_i]; }
sumit_dutta there is a segmentaion fault in your code.
ben_nxumalo $first = $second=0; $j = $n-1; for($i=0;$i<$n; $i++){ $first +=$a[$i][$i]; $second +=$a[$i][$j]; $j--; } $result= abs($first-$second); print abs($result);
Turings_Ghost Slightly cleaner and more readable:
int diag1 = 0, diag2 = 0; for(int p = 0; p<n; p++) { diag1 += a[p][p]; diag2 += a[p][n - (p + 1)]; }prachigoel1598 can u please explain why n-j-1...
post4visakhvspm because n will be length and always +1 than index
bhargavisri Can you please explain me
firstDiagonal+=a.at(i).at(i); secondDiagonal+=a.at(count).at(i);
gaganbaheti_it20 you will get an error. i tested your code and it's showing error
jesus_rpalos I had no problem running my code when I submitted.
Turings_Ghost Every "for" has a condition. If you mean no "if" or other explicit condition statements, sure.
ckastam that's in int main....not in the function....
suketmehtani [deleted]pycraft114 this is so wrong answer . O(N^2) is way worse then O(N)
irvision_bsb 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.".
santhosh_sunkari good
shk161 cool :) am noob coder! wasted 40 mins for this logic but finally happy.
Appatucker You are not wasting any time when you are coding. You will always learn something if it takes sometime and you finish it. :)
md_faisal absolutely right.....
manasveemittal explain this to facebook co-founders. They actually learnt how to feel cheated by the better croook.
forrest_A_K_I_N same!
Tritonal 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.
AllisonP 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".
ignacio_rafael I did the Math on the reading loop:
var d1_v = 0; var d2_v = 0; for(int a_i = 0; a_i < n; a_i++){ string[] a_temp = Console.ReadLine().Split(' '); a[a_i] = Array.ConvertAll(a_temp,Int32.Parse); d1_v += a[a_i][a_i]; d2_v += a[a_i][(n - 1) - a_i]; } Console.WriteLine(Math.Abs(d1_v - d2_v));JocoMagic Hey there could you add an explanation as to what your code does, i would appreciate it. Thanks in advance.
Taylor40 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.
dass_2808 Nice work dude...!!
syedfarrufar did the same in c but i didnt get the output
paulclift I used this as a basis for my c# submission as I was quite stumped.
misgevolution int sum1=0,sum2=0; for(int i=0, k=size-1; i< size; i++){ for(int j=0; j< size; j++){ cin >> matrix[i][j]; if(i==j) sum1 += matrix[i][j]; } sum2 += matrix[i][k]; k -= 1; } cout << abs(sum1-sum2);
Joxebus [deleted]
souman1729 good thinking
jefflima Really nice one.
You can actually move up the k -= 1 into the outer loop next to the i++ as:
int sum1=0,sum2=0; for(int i=0, k=size-1; i< size; i++, k--){ for(int j=0; j< size; j++){ cin >> matrix[i][j]; if(i==j) sum1 += matrix[i][j]; } sum2 += matrix[i][k]; } cout << abs(sum1-sum2);
misgevolution Yes, thanks!
Deeps79 what's the use of k here?? k=size-1...and k-- ? can Anyone help out..please
abhijith4514 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.
aviral16austy yes I dont get k? i reprents rows,j represents columns i think but k?
aman1996esseffc1 well you can use i in place of k that's not a problem that's just a variable used for looping
Kanahaiya Here is the video explaination- https://youtu.be/f6bTIsj9ne8
vinay666 good
lemueluhuru Nice. You can remove the conditional though, and complete this in one loop. Here is my solution in JavaScript.
let primaryDiag = 0 let secondDiag = 0 let length = Matrix.length for (var i = 0, indexLength = length - 1; i < length; i++) { primaryDiag += Matrix[i][i] secondaryDiag += Matrix[i][indexLength] indexLength -= 1 } return Math.abs(primaryDiag - secondaryDiag)tinla14 Hello lemuel,
Can you please explain more to me about this????
jonathan_m_whit1 I altered a little.
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)}
suhailmdcse super!! logic
sedhuramMV Nice logic :)
unovongalixor there's no need for nested for loops:
matrix_size = int(input()) current_x_one = 0 current_x_two = matrix_size - 1 sum_one = 0 sum_two = 0 for line in range(matrix_size): input_string = input().split(" ") sum_one = sum_one + int(input_string[current_x_one]) sum_two = sum_two + int(input_string[current_x_two]) current_x_one += 1 current_x_two -= 1 print(abs(sum_one - sum_two))AllisonP 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.
gabrielguelfi [deleted]gabrielguelfi Well, it added to me.
prlpzb [deleted]msambitkumar1991 @allison it is all about algorithmic appraoch. A person can use any language to exhibit his/her ideas IMO.
sagemode 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!
AllisonP 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(); }sagemode [deleted]sagemode 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.
for(int j = 0; j < numInputs; j++){ for(int k = 0; k < numInputs; k++){ cin >> curInput; if(j == k){ leftD += curInput; } if(j+k == (numInputs-1)){ rightD += curInput; } } }Yours Java equivalent solution to Python looks so hard to read.
Look at this Python solution:
n = int(input().strip()) dSumLeft = 0 dSumRight = 0 for i in range(n): matrixRow = input().split() dSumLeft += int(matrixRow[i]) dSumRight += int(matrixRow[-(i + 1)])Simple and Powerful!
We need to learn and understand the balance required between performance and memory usage.
AllisonP 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.
sagemode 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!
danielhernanrico 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.
manasveemittal #!/bin/python import sys ''' n = int(raw_input().strip()) a = [] for a_i in xrange(n): a_temp = map(int,raw_input().strip().split(' ')) a.append(a_temp) z1,z2 = 0,0 for x1 in range(n): z1 += a[x1][x1] for x1 in range(n): z2 += a[x1][n-x1-1] print z1,z2 ''' n = int(input().strip()) dSumLeft = 0 dSumRight = 0 for i in range(n): matrixRow = input().split() dSumLeft += int(matrixRow[i]) dSumRight += int(matrixRow[-(i + 1)]) print dSumLeft-dSumRight
neither my code , nor yours is printing, please point the error
marttidumangeng try this
#!/bin/python import sys n = int(raw_input().strip()) dSumLeft = 0 dSumRight = 0 for i in range(n): matrixRow = map(int,raw_input().strip().split(' ')) dSumLeft += int(matrixRow[i]) dSumRight += int(matrixRow[n-i-1]) print abs(dSumLeft - dSumRight)
christopher_bir1 Here is a python 3 version below:
n = int(input().strip()) dSumLeft = 0 dSumRight = 0 for i in range(n): matrixRow = list(map(int,input().strip().split(' '))) dSumLeft += int(matrixRow[i]) dSumRight += int(matrixRow[n-i-1]) print(abs(dSumLeft - dSumRight))
bL4ck_r4bb1t [deleted]
ak311 plz explain
toaa_kama2354 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.
def diagonalDifference(a): # Complete this function sum1 = 0 sum2 = 0 for i in range(n): sum1 += int(a[i][i]) sum2 += int(a[i][n-i-1]) return abs(sum1 - sum2)
shreeshailgumge1 Awesome bro. U keep it simple
aswinirathi1000 n is not defined inside this function . then how can you use n inside this fun
CodeRanger_121 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)
h150040481 That python code was brilliant
sandeep_ch41 [deleted]pgilescapone 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.
//first diagonal int fd = 0; for (int i=0; i < n; i++) { fd += a[i][i]; } //second diagonal int sd = 0; int x = 0; int y = n-1; for (int j=0; j < n; j++) { sd += a[x++][y--]; } int answer = Math.abs(sd-fd); System.out.println(answer);
_rok_zigon very elegant solution, mine was similar:
for (var j = n-1, k = 0; j > -1; j--, k++ ) { diagonalB += arr[k][j]; }
148W1A1237 You are great
xisreal 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 ;)
rajarshi356 since i am a beginner will you please tell me what is the function of .split ?
sarinarw 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"].
bogdanh 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.
public static void main(String[] args) { Scanner in = new Scanner(System.in); int N = in.nextInt(); int sumA =0, sumB = 0; int M = N*N; //counter for first diagonal int countA = N-N; // 0 -> N*N ; step N+1 // counte for second diagonal int countB = N-1; // N-1 -> N*N-N; step N-1 int countBLimit = M-1; // the last element is not for this diagonal for (int i = 0; i<M; i++) { int k = 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)); }
rajarshi356 Thnx a lot
ArunkumarNR what is the need to parse the value to integer?
misgevolution There is no performance improvement in unfolding the 2d matrix in to 1d. Thats what you did here.
gabrielguelfi 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!
gabrielguelfi [deleted]gabrielguelfi 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!
misgevolution 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.
Ardillo It can be as simple as a line:
print(abs(sum([a[i][i] - a[i][n-i-1] for i in range(n)])))
themightyscot the square brackets around the difference/range part of the statement are not necessary.
an0o0nym Little bit tweaked example from above:
n = int(input()) diagonal1, diagonal2 = 0, 0 for i in range(n): row = input().split() diagonal1 += int(row[i]) diagonal2 += int(row[n-1-i]) print(abs(diagonal1-diagonal2))
ajinkya_patankar input().split() gives error
row = input().split()EOFError: EOF when reading a line
OJ1010 This is great. I don't understand it much though... can anyone help?
reddyjahnavi Thanks a lot!!
michelbetancour1 one liner python
print(abs(sum((lambda arr: int(arr[x]) - int(arr[len(arr) - x - 1]))(input().split()) for x in range(int(input())))))
other approach
n = int(input().strip()) result = 0 for x in range(n): arr = input().strip().split() result += int(arr[x]) - int(arr[n - x - 1]) print(abs(result))
MR_MECHANICAL Similair code
a=int(input()) x=[] rd=0 ld=0 c=a-1 for i in range(a): x.append(input().split()) rd+=(int(x[i][i])) ld+=(int(x[i][c])) c-=1 print(abs(rd-ld))
sankaranarayana1 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..
Draded //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);sagemode 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.
szhao13 Could someone help me understand what's happening with the line "cin >> curInput;"?
AllisonP 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;.szhao13 Ok, so it's not bitshifting? I thought the >> operator was for right bitshift, which is why I was so confused.
AllisonP 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.
zarak Just a small aside - these IO operators were introduced in C++ - they don't exist in C.
coding_rj 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.)
j_delemosmartin sorry but i did not understand this properly. Can you explain it clearly please? Thank you in advance.
jainvinay143 awesome
ryerabaka 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.
AllisonP 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.
luisB 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
Suraj_025 whats about the number which is common in both digonal....
khuongduybui I don't even bother storing leftD and rightD.
if(j == k) { result += curInput; } if(j+k+1 == numInputs) { result -= curInput; } ans = abs(result);
nh2amine result += ((j == k) - (j+k+1 == numInputs)) * curInput;khuongduybui Looks cool, but I don't like using bools for their binary values.
allano #!/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/-//'`
gabrielguelfi 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.
Ardillo Watch this:
print(abs(sum([a[i][i] - a[i][n-i-1] for i in range(n)])))
philipyoo Can someone explain what this line does?:
cin >> curInput;hacker_vwdz2zxx 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.
underscore77 A very clean solution, thank's for share ur algorithm ;)
fatboycodes Cool!
rishin458 I did something similar. :)
int main(){ int n,*p,i,j,sum,k; scanf("%d",&n); p = (int *)calloc(n,sizeof(int)); for(i=0;i <= n*n - 1;i++) scanf("%d",&p[i]); j=0;k=n-1;sum=0; for(i=1;i<=n;i++) { sum += p[j]; sum -= p[k]; j += n+1; k += n-1; } printf("%d",abs(sum)); return 0;}
ashishdalal_yes its not working for me
ranju73 Super cool yar!!
magedmakar Why complexity of nested loop? This is how I solved it:
long sum1 = 0; long sum2 = 0;
for (int i = 0; i < n ; i++) { sum1 += a[i][i]; sum2 += a[i][n - 1 - i]; } Console.WriteLine(Math.Abs(sum1 - sum2));
shreeharshas This is what I did too! Takes O(n) time. Cheers!
ypahalajani Did the same in Java [ O(n) time complexity ]:
for(int i=0; i<n; i++){ sum1+=arr[i][i]; sum2+=arr[i][n-1-i]; } System.out.println(Math.abs(sum1-sum2));15131A1284_meera why did keep + symbols infroont of sum1 and sum2..?
ShreyaKotteda its like SUM=SUM+arr[i][i];
The + indicated that ^
HarshitAgrawal95 Amazing Man!! The solution is just AMAZING !!
shreeharshas 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?
c4m170 Nice!
jaychaturvedi really cool approach
prateeksharmamay It means you are just considering the input values when the if conditions are true, otherwise all other values are discarded. Right ?
prateekskit Thats Perfect !!
sankaranarayana1 superb sir hats off.......
m_amit nicely done
ZeroXLR 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.
tl255 This one is so cool and clear, thanks for sharing.
sachinsreedar92 public static int arraySum(int[][] array){ int total = 0;
for (int row = 0; row < array.length; row++) { total += array[row][row]; } return total;}
jyoti273 Nice approach
fritzmatias You are using 2 variables "left and rigth" when you can use only one. wich one should be incremented and decremented.
dancinglightning Second loop (k) is not needed, index can be caluculated from array dimension and j
abhivasu this logic (j+k==n-1)is short and precise
pardesinilesh nice one!
Devbag 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));bismeetsingh352 What is the curInput used for?
Devbag The current input :) cin >>> curInput.
balyan wow, awesome man you showed me a whole new way to look at this problem.
ankitcoder28 now it's look like a algorithm domain...
Abhimessi_fcb cool..bro
davidxavier378 it is the best solution of the question given and it is good even for large value of N;
sjmulder I did about the same, but using a single for loop and a single sum variable:
#include <stdio.h> #include <stdlib.h> int main(void) { int sz; scanf("%d", &sz); int sum = 0; for (int i = 0; i < sz*sz; i++) { int x; scanf("%d", &x); if (!(i % (sz+1))) sum += x; if (i > sz-2 && i < sz*sz-1 && !(i % (sz-1))) sum -= x; } printf("%d\n", abs(sum)); }
asadullonurulla1 thanks
hirenjagani nice approch , solution is quite good
se61990 Cool !!!
DiegoS it was my condition for show an different example
if(a_i==(n-a_j-1))
koolkaju 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]; }skhan75 this won't work for an odd square matrix like 3x3, 5x5, 7x7
paul_felkner 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.
paul_felkner Thank you very much for the quick reply :)
azar1019 Very intersting solution.
Silver_Shark i tried with this method but it is showing terminated due to timeout
abhishekp03 Great Dude! if(j+k == (numInputs-1))
sandip1805 if(j+k == (numInputs-1))
really instresting logic. how you find this?
abhishekp03 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.
wogkr2618 How can I use like this code in Java
Sorry I'm a beginner haha
chetankh23 Great !!
imh1j4l great thinking :D
piyushrocks123 Interesting !!
j_delemosmartin sorry but i did not understand the "cin >> curInput" line :(
arpit719 awesome bro !!
tonybui Haha without using array approach is very cool.
topeth Brilliant!
rinu_budhbhatti what would be the numInputs here, example plz.
uyr_sust please explain it.
stv_yang10 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!
puneethts 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); }
wdoering What does this do? If this is a bit shift, what is the purpose?
cin >> curInput;kachi_kinjal if(j+k == (numInputs-1)) You are awesome :)
CHODHARY 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
gunjan_utsav you are good in math,certainly!
ben_nxumalo second=0; n-1; for(i<i++){ a[i]; a[j]; $j--; }
samaiyar wow.. surely a thing to learn
nomadevproject nice approach!
hydragon that is more nicer way than the way i did it k == (size-1)-j
shanuraj1995 awesome logic dude
m0g Awful solution, it takes O(n^2) which is quadratic time, this does not scale. No idea why people are cheering this code.
VaibhavMagon Awesome!
akashsharma22441 It's Simply so brilliant!!!
cameronroe Aren't nested for loops a performance bottleneck? They perscribe to O(n^2) right? Isn't that unscalable?
rishikra5 why is there (numinputs-1) and not (numinputs+1)?
rachitex 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.
hackaroo Did this in python
n = len(a) ans = 0 for i in xrange(n): ans+=a[i][i] - a[i][n-i-1] print abs(ans)
andalltheworldi1 Wow that makes my version of this super dirty in comparison.
jesus_rpalos 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.
int rightD = 0; int leftD = 0; for(int i = 0; i < n; i++){ leftD += a[i][i]; rightD += a[i][n-i-1]; } System.out.println(Math.abs(leftD - rightD));
pbelasco Came to the same result, but ruby way. Just one loop
diag1=diag2=0 for i in (0...n) diag1 += a[i][i] diag2 += a[i][n-i-1] end puts (diag1-diag2).abs
patrickclery Crazy! I got the EXACT same. Important to note you have to pass
nto the function.def diagonalDifference(a,n) # Complete this function x = y = 0 for i in (0...n) x += a[i][i] y += a[i][n-1-i] end puts (x-y).abs end
nouriyouri N can be deduced from Array size I wrote this :
def diagonalDifference(arr) # Write your code here primary = arr.map.with_index { |line, i| line[i] }.sum secondary = arr.map.with_index { |line, i| line[-i.next] }.sum return (primary - secondary).abs end
deep5_rana 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))
Sort 3219 Discussions, By:
Please Login in order to post a comment