We have given a spiral matrix of odd-order, in which we start with the number 1 as center and moving to the right in a clockwise direction.
Examples :
Input : n = 3 Output : 25 Explanation : spiral matrix = 7 8 9 6 1 2 5 4 3 The sum of diagonals is 7+1+3+9+5 = 25 Input : n = 5 Output : 101 Explanation : spiral matrix of order 5 21 22 23 23 25 20 7 8 9 10 19 6 1 2 11 18 5 4 3 12 17 16 15 14 13 The sum of diagonals is 21+7+1+3+13+ 25+9+5+17 = 101
If we take a closer look at the spiral matrix of n x n, we can notice that top right corner element has value n2. Value of top left corner is (n^2) – (n-1) [Why? not that we move ant-clockwise in spiral matrix, therefore we get value of top left after subtracting n-1 from top right]. Similarly values of bottom left corner is (n^2) – 2(n-1) and bottom right corner is (n^2) – 3(n-1). After adding all the four corners we get 4[(n^2)] – 6(n-1).
Let f(n) be sum of diagonal elements for a n x n matrix. Using above observations, we can recursively write f(n) as:
f(n) = 4[(n^2)] – 6(n-1) + f(n-2)
From above relation, we can find the sum of all diagonal elements of a spiral matrix with the help of iterative method.
spiralDiaSum(n)
{
if (n == 1)
return 1;
// as order should be only odd
// we should pass only odd-integers
return (4*n*n - 6*n + 6 + spiralDiaSum(n-2));
}
Below is the implementation.
C++
// C++ program to find sum of // diagonals of spiral matrix #include<bits/stdc++.h> using namespace std; // function returns sum of diagonals int spiralDiaSum(int n) { if (n == 1) return 1; // as order should be only odd // we should pass only odd-integers return (4*n*n - 6*n + 6 + spiralDiaSum(n-2)); } // Driver program int main() { int n = 7; cout << spiralDiaSum(n); return 0; } |
Java
// Java program to find sum of // diagonals of spiral matrix class GFG { // function returns sum of diagonals static int spiralDiaSum(int n) { if (n == 1) return 1; // as order should be only odd // we should pass only odd-integers return (4 * n * n - 6 * n + 6 + spiralDiaSum(n - 2)); } // Driver program to test public static void main (String[] args) { int n = 7; System.out.print(spiralDiaSum(n)); } } // This code is contributed by Anant Agarwal. |
Python3
# Python3 program to find sum of # diagonals of spiral matrix # function returns sum of diagonals def spiralDiaSum(n): if n == 1: return 1 # as order should be only odd # we should pass only odd # integers return (4 * n*n - 6 * n + 6 + spiralDiaSum(n-2)) # Driver program n = 7; print(spiralDiaSum(n)) # This code is contributed by Anant Agarwal. |
C#
// C# program to find sum of // diagonals of spiral matrix using System; class GFG { // function returns sum of diagonals static int spiralDiaSum(int n) { if (n == 1) return 1; // as order should be only odd // we should pass only odd-integers return (4 * n * n - 6 * n + 6 + spiralDiaSum(n - 2)); } // Driver code public static void Main (String[] args) { int n = 7; Console.Write(spiralDiaSum(n)); } } // This code is contributed by parashar... |
PHP
<?php // PHP program to find sum of // diagonals of spiral matrix // function returns sum // of diagonals function spiralDiaSum( $n) { if ($n == 1) return 1; // as order should be only odd // we should pass only odd-integers return (4 * $n * $n - 6 * $n + 6 + spiralDiaSum($n - 2)); } // Driver Code $n = 7; echo spiralDiaSum($n); // This code is contributed by anuj_67. ?> |
Javascript
<script> // Javascript program to find sum of // diagonals of spiral matrix // function returns sum of diagonals function spiralDiaSum(n) { if (n == 1) return 1; // as order should be only odd // we should pass only odd-integers return (4*n*n - 6*n + 6 + spiralDiaSum(n-2)); } // Driver program let n = 7; document.write(spiralDiaSum(n)); </script> |
Output :
261
Time complexity: O(n).
Auxiliary Space: O(n), as implicit stack is created due to recursive call
This article is contributed by Aarti_Rathi and Shivam Pradhan . If you like neveropen and would like to contribute, you can also write an article using write.neveropen.co.za or mail your article to review-team@neveropen.co.za. See your article appearing on the neveropen main page and help other Geeks.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!