Find the element at the specified index of a Spirally Filled Matrix
Given two integers x and y representing the row and column number in a matrix respectively, the task is to find the integer at the cell (x, y) in the Spirally Filled Matrix.
Explanation:
The size of the matrix change according to the insertion of elements.
As the row and columns are filled layer – by – layer, a square matrix will be formed as each row and column are added simultaneously in the following manner:
- A square matrix of size 1 x 1 is formed having a single element 1.
- A square matrix of size 2 x 2 is formed after spiral insertion of elements {2, 3, 4} in order:
{{1, 2},
{4, 3}}- A square matrix of size 3 x 3 is formed after spiral insertion of elements {5, 6, 7, 8} in order:
{{1, 2, 9},
{4, 3, 8},
{5, 6, 7}}
Below image denotes a 4*4 matrix generated following the above steps:
Examples:
Input: X = 2, Y = 3
Output: 8
Explanation:
The element at row 2 and column 3 is 8.Input: X = 5, Y = 4
Output: 20
Explanation: The element at row 5 and column 4 is 20.
Approach:
To solve the problem, the logic behind the given spirally filled matrix needs to be understood. Following are the possible cases that need to be considered:
- Case 1: If y > x & y is odd
The element at (x, y) is equal to y2 – x +1
Illustration:
y = 3, x = 1
y2 – x +1 = 9 – 1 + 1 = 9
Element present at (1, 3) = 9.
- Case 2: If y > x & y is even
The element at (x, y) is equal to (y – 1)2 + x
Illustration:
y = 4, x = 1
(y – 1)2 + x = 9 + 1 = 10
Element present at (1, 4) = 10.
- Case 3: If x ? y & x is even
The element at (x, y) is equal to x2 – y +1
Illustration:
y = 1, x = 4
x2 – y + 1 = 16 – 1 + 1 = 16
Element present at (4, 1) = 16.
- Case 4: If If x ? y & x is odd
The element at (x, y) is equal to (x – 1)2 + y
Illustration:
y = 2, x = 3
(x – 1)2 + y = 4 + 2 = 6
Element present at (3, 2) = 6.
Hence, in order to solve the problem, we need to evaluate and print the result of the equation corresponding to the condition which the given x and y satisfy.
Below is the implementation of the above approach:
C++
// C++ Program to find the element // at given position in spirally // filled matrix #include <bits/stdc++.h> using namespace std; // Function to return the // element at (x, y) int SpiralElement( int x, int y) { int r; // If y is greater if (x < y) { // If y is odd if (y % 2 == 1) { r = y * y; return (r - x + 1); } // If y is even else { r = (y - 1) * (y - 1); return (r + x); } } else { // If x is even if (x % 2 == 0) { r = x * x; return (r - y + 1); } // If x is odd else { r = (x - 1) * (x - 1); return (r + y); } } } // Driver Code int main() { int x = 2, y = 3; cout << SpiralElement(x, y); return 0; } |
Java
// Java program to find the element // at given position in spirally // filled matrix import java.util.*; class GFG{ // Function to return the // element at (x, y) static int SpiralElement( int x, int y) { int r; // If y is greater if (x < y) { // If y is odd if (y % 2 == 1 ) { r = y * y; return (r - x + 1 ); } // If y is even else { r = (y - 1 ) * (y - 1 ); return (r + x); } } else { // If x is even if (x % 2 == 0 ) { r = x * x; return (r - y + 1 ); } // If x is odd else { r = (x - 1 ) * (x - 1 ); return (r + y); } } } // Driver code public static void main(String[] args) { int x = 2 , y = 3 ; System.out.println(SpiralElement(x, y)); } } // This code is contributed by offbeat |
Python3
# Python3 program to find the element # at given position in spirally # filled matrix # Function to return the # element at (x, y) def SpiralElement(x, y): r = 0 # If y is greater if (x < y): # If y is odd if (y % 2 = = 1 ): r = y * y return (r - x + 1 ) # If y is even else : r = (y - 1 ) * (y - 1 ) return (r + x) else : # If x is even if (x % 2 = = 0 ): r = x * x return (r - y + 1 ) # If x is odd else : r = (x - 1 ) * (x - 1 ) return (r + y) # Driver code if __name__ = = '__main__' : x = 2 y = 3 print (SpiralElement(x, y)) # This code is contributed by Amit Katiyar |
C#
// C# program to find the element // at given position in spirally // filled matrix using System; class GFG{ // Function to return the // element at (x, y) static int SpiralElement( int x, int y) { int r; // If y is greater if (x < y) { // If y is odd if (y % 2 == 1) { r = y * y; return (r - x + 1); } // If y is even else { r = (y - 1) * (y - 1); return (r + x); } } else { // If x is even if (x % 2 == 0) { r = x * x; return (r - y + 1); } // If x is odd else { r = (x - 1) * (x - 1); return (r + y); } } } // Driver code static public void Main() { int x = 2, y = 3; Console.WriteLine(SpiralElement(x, y)); } } // This code is contributed by offbeat |
Javascript
<script> // javascript program to find the element // at given position in spirally // filled matrix // Function to return the // element at (x, y) function SpiralElement(x , y) { var r; // If y is greater if (x < y) { // If y is odd if (y % 2 == 1) { r = y * y; return (r - x + 1); } // If y is even else { r = (y - 1) * (y - 1); return (r + x); } } else { // If x is even if (x % 2 == 0) { r = x * x; return (r - y + 1); } // If x is odd else { r = (x - 1) * (x - 1); return (r + y); } } } // Driver code var x = 2, y = 3; document.write(SpiralElement(x, y)); // This code contributed by gauravrajput1 </script> |
8
Time complexity: O(1)
Auxiliary Space: O(1)
Contact Us