Find the sum of the diagonal elements of the given N X N spiral matrix

0 0 6 minutes read

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 matrix
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 code
int main()
{
    int n = 4;
 
    cout << findSum(n);
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
public class GFG
{
   
// Function to return the sum of both the
// diagonal elements of the required matrix
static 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 code
public 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 matrix
def 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 code
if __name__ == '__main__':
    n = 4
 
    print(findSum(n))
 
# This code is contributed by
# Samim Hossain Mondal

C#

// C# implementation of the approach
using System;
 
class GFG
{
   
// Function to return the sum of both the
// diagonal elements of the required matrix
static 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 code
public 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 matrix
function 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 code
let n = 4;
document.write(findSum(n));
 
// This code is contributed by Samim Hossain Mondal.
</script>

Output

Time Complexity: O(2^N)

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 matrix
int 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 code
int main()
{
    int n = 4;
 
    cout << findSum(n);
 
    return 0;
}

Java

// Java implementation of the approach
class GFG
{
     
// Function to return the sum of both the
// diagonal elements of the required matrix
static 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 code
public 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 matrix
def 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 code
if __name__ == '__main__':
    n = 4
 
    print(findSum(n))
 
# This code is contributed by
# Surendra_Gangwar

C#

// C# implementation of the approach
 
class GFG
{
     
// Function to return the sum of both the
// diagonal elements of the required matrix
static 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 code
static 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 matrix
function 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 matrix
let 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 code
let n = 4;
 
document.write(findSum(n));
 
// This code is contributed by rishavmahato348.
</script>

Output

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 zambiatek!