Given N which is the size of the N X N spiral matrix of the form:
16 15 14 13 5 4 3 12 6 1 2 11 7 8 9 10
The task is to find the sum of the diagonal elements of this matrix.
Examples:
Input: N = 3 Output: 25 5 4 3 6 1 2 7 8 9 The sum of elements along its two diagonals will be 1 + 3 + 7 + 5 + 9 = 25 Input: N = 5 Output: 101
Recursive Approach: The idea behind the solution is to use recursion to compute sum of the diagonal elements.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the sum of both the// diagonal elements of the required matrixint findSum(int n){ // Base cases if(n == 0) { return 0; } if(n == 1) { return 1; } int ans = 0; // Computing for ans for (int i = 2; i <= n; i++) { ans =(4 * (i * i)) - 6 * (i - 1) + findSum(n - 2); } // Return ans; return ans;}// Driver codeint main(){ int n = 4; cout << findSum(n); return 0;} |
Java
// Java implementation of the approachimport java.util.*;public class GFG{ // Function to return the sum of both the// diagonal elements of the required matrixstatic int findSum(int n){ // Base cases if(n == 0) { return 0; } if(n == 1) { return 1; } int ans = 0; // Computing for ans for (int i = 2; i <= n; i++) { ans =(4 * (i * i)) - 6 * (i - 1) + findSum(n - 2); } // Return ans; return ans;}// Driver codepublic static void main(String args[]){ int n = 4; System.out.println(findSum(n)); }}// This code is contributed by Samim Hossain Mondal. |
Python3
# Python 3 implementation of the approach# Function to return the sum of both the# diagonal elements of the required matrixdef findSum(n): # Base cases if(n == 0): return 0 if(n == 1): return 1 ans = 0 # Computing for ans for i in range(2, n + 1, 1): ans = ((4 * (i * i)) - 6 * (i - 1) + findSum(n - 2)) return ans# Driver codeif __name__ == '__main__': n = 4 print(findSum(n))# This code is contributed by# Samim Hossain Mondal |
C#
// C# implementation of the approachusing System;class GFG{ // Function to return the sum of both the// diagonal elements of the required matrixstatic int findSum(int n){ // Base cases if(n == 0) { return 0; } if(n == 1) { return 1; } int ans = 0; // Computing for ans for (int i = 2; i <= n; i++) { ans =(4 * (i * i)) - 6 * (i - 1) + findSum(n - 2); } // Return ans; return ans;}// Driver codepublic static void Main(){ int n = 4; Console.Write(findSum(n)); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script>// Javascript implementation of the approach// Function to return the sum of both the// diagonal elements of the required matrixfunction findSum(n){ // Base cases if(n == 0) { return 0; } if(n == 1) { return 1; } let ans = 0; // Computing for ans for (let i = 2; i <= n; i++) { ans =(4 * (i * i)) - 6 * (i - 1) + findSum(n - 2); } // Return ans; return ans;}// Driver codelet n = 4;document.write(findSum(n));// This code is contributed by Samim Hossain Mondal.</script> |
Output
56
Time Complexity: O(2N)
Auxiliary Space: O(1)
Dynamic Programming Approach: Idea behind the solution is to use the concept of Dynamic Programming. We will use array dp[] to store our solution. N given in the problem can either be even or odd.
When i is odd, we have to add only 4 corner elements in dp[i – 2].
dp[i] = dp[i – 2] + (i – 2) * (i – 2) + (i – 1) + (i – 2) * (i – 2) + 2 * (i – 1) + (i – 2) * (i – 2) + 3 * (i – 1) + (i – 2) * (i – 2) + 4 * (i – 1)
dp[i] = dp[i – 2] + 4 * (i – 2) * (i – 2) + 10 * (i – 1)
dp[i] = dp[i – 2] + 4 * (i) * (i) – 6 * (i – 1)
Similarly, we can check that the above formula is true when i is even.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the sum of both the// diagonal elements of the required matrixint findSum(int n){ // Array to store sum of diagonal elements int dp[n + 1]; // Base cases dp[1] = 1; dp[0] = 0; // Computing the value of dp for (int i = 2; i <= n; i++) { dp[i] = (4 * (i * i)) - 6 * (i - 1) + dp[i - 2]; } return dp[n];}// Driver codeint main(){ int n = 4; cout << findSum(n); return 0;} |
Java
// Java implementation of the approachclass GFG{ // Function to return the sum of both the// diagonal elements of the required matrixstatic int findSum(int n){ // Array to store sum of diagonal elements int[] dp = new int[n + 1]; // Base cases dp[1] = 1; dp[0] = 0; // Computing the value of dp for (int i = 2; i <= n; i++) { dp[i] = (4 * (i * i)) - 6 * (i - 1) + dp[i - 2]; } return dp[n];}// Driver codepublic static void main(String args[]){ int n = 4; System.out.println(findSum(n));}}// This code is contributed by Akanksha Rai |
Python3
# Python 3 implementation of the approach# Function to return the sum of both the# diagonal elements of the required matrixdef findSum(n): # Array to store sum of diagonal elements dp = [0 for i in range(n + 1)] # Base cases dp[1] = 1 dp[0] = 0 # Computing the value of dp for i in range(2, n + 1, 1): dp[i] = ((4 * (i * i)) - 6 * (i - 1) + dp[i - 2]) return dp[n]# Driver codeif __name__ == '__main__': n = 4 print(findSum(n))# This code is contributed by# Surendra_Gangwar |
C#
// C# implementation of the approachclass GFG{ // Function to return the sum of both the// diagonal elements of the required matrixstatic int findSum(int n){ // Array to store sum of diagonal elements int[] dp = new int[n + 1]; // Base cases dp[1] = 1; dp[0] = 0; // Computing the value of dp for (int i = 2; i <= n; i++) { dp[i] = (4 * (i * i)) - 6 * (i - 1) + dp[i - 2]; } return dp[n];}// Driver codestatic void Main(){ int n = 4; System.Console.WriteLine(findSum(n));}}// This code is contributed by mits |
PHP
<?php// PHP implementation of the approach// Function to return the sum of both the// diagonal elements of the required matrixfunction findSum($n){ // Array to store sum of diagonal elements $dp = array(); // Base cases $dp[1] = 1; $dp[0] = 0; // Computing the value of dp for ($i = 2; $i <= $n; $i++) { $dp[$i] = (4 * ($i * $i)) - 6 * ($i - 1) + $dp[$i - 2]; } return $dp[$n];}// Driver code$n = 4;echo findSum($n);// This code is contributed by Akanksha Rai?> |
Javascript
<script>// Javascript implementation of the approach// Function to return the sum of both the// diagonal elements of the required matrixlet findSum(n){ // Array to store sum of diagonal elements let dp = new Array(n + 1); // Base cases dp[1] = 1; dp[0] = 0; // Computing the value of dp for (let i = 2; i <= n; i++) { dp[i] = (4 * (i * i)) - 6 * (i - 1) + dp[i - 2]; } return dp[n];}// Driver codelet n = 4;document.write(findSum(n));// This code is contributed by rishavmahato348.</script> |
Output
56
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
