CSES Solutions - Number Spiral

A number spiral is an infinite grid whose upper-left square has the number 1. The task is to find the number in row Y and column X. Here are the first five layers of the spiral:

Examples:

Input: Y = 2, X = 3
Output: 8
Explanation: The 2nd row, 3rd column contains 8.

Input: Y = 4, X = 2
Output: 15
Explanation: The 4th row, 2nd column contains 15.

Approach: To solve the problem, follow the below idea:

It can be observed that grid consists of many squares and the values at boundaries of the square is either in increasing or decreasing order. The answer lies at the boundary of the square whose side is the maximum of Y or X. So now to get the value at Yth row and Xth column we can compute the area of inner square whose side is just one less than the side of square whose boundary contains the answer. The remaining value can be added to the area of inner square by checking the parity of Minimum of Y or X. It can be observed that for even row in the grid, the numbers are in decreasing order, and for the odd row the numbers are in increasing order in the anticlockwise direction.

Step-by-step algorithm:

• Compare Y and X:
• If Y>X:
  • Compute the area of inner square which (Y-1)*(Y-1). This represents the numbers which are not on the boundary of the square which contains the answer.
  • Now to add the remaining numbers which are on the boundary, check the parity of Yth row, if the Yth row is odd then simply add X to the area of inner square or else add (2*Y - X) to the area.
• Else:
  • Similarly, compute the area of inner square which (X-1)*(X-1). This represents the numbers which are not on the boundary of the square which contains the answer.
  • Now to add the remaining numbers which are on the boundary, check the parity of Xth column, if the Xth column is even then simply add Y to the area of inner square or else add (2*X - Y) to the area. This will give the final answer.

Below is the implementation of above approach:

#include <bits/stdc++.h> using namespace std; typedef long long ll; // Function to compute the value at position (Y, X) in the // number spiral void NumberSpiral(ll Y, ll X) {  // If Y is greater than X, implying Yth row is the outer  // boundary  if (Y > X) {  // Compute the area of the inner square  ll ans = (Y - 1) * (Y - 1);  ll add = 0;  // Check parity of Y to determine if numbers are in  // increasing or decreasing order  if (Y % 2 != 0) {  // Add X to the area if Yth row is odd  add = X;  }  else {  // Add 2*Y - X to the area if Yth row is even  add = 2 * Y - X;  }  // Print the final result  cout << ans + add << "\n";  }  // If X is greater than or equal to Y, implying Xth  // column is the outer boundary  else {  // Compute the area of the inner square  ll ans = (X - 1) * (X - 1);  ll add = 0;  // Check parity of X to determine if numbers are in  // increasing or decreasing order  if (X % 2 == 0) {  // Add Y to the area if Xth column is even  add = Y;  }  else {  // Add 2*X - Y to the area if Xth column is odd  add = 2 * X - Y;  }  // Print the final result  cout << ans + add << "\n";  } } // Driver Code int main() {  ll Y = 2, X = 3;  NumberSpiral(Y, X); } 

import java.util.*; public class NumberSpiral {  // Function to compute the value at position (Y, X) in the number spiral  static void numberSpiral(long Y, long X) {  // If Y is greater than X, implying Yth row is the outer boundary  if (Y > X) {  // Compute the area of the inner square  long ans = (Y - 1) * (Y - 1);  long add;  // Check parity of Y to determine if numbers are in increasing or decreasing order  if (Y % 2 != 0) {  // Add X to the area if Yth row is odd  add = X;  } else {  // Add 2*Y - X to the area if Yth row is even  add = 2 * Y - X;  }  // Print the final result  System.out.println(ans + add);  }  // If X is greater than or equal to Y, implying Xth column is the outer boundary  else {  // Compute the area of the inner square  long ans = (X - 1) * (X - 1);  long add;  // Check parity of X to determine if numbers are in increasing or decreasing order  if (X % 2 == 0) {  // Add Y to the area if Xth column is even  add = Y;  } else {  // Add 2*X - Y to the area if Xth column is odd  add = 2 * X - Y;  }  // Print the final result  System.out.println(ans + add);  }  }  // Driver Code  public static void main(String[] args) {  long Y = 2, X = 3;  numberSpiral(Y, X);  } } // This code is contributed by akshitaguprzj3 

def number_spiral(Y, X): # If Y is greater than X, implying Yth row is the outer boundary if Y > X: # Compute the area of the inner square ans = (Y - 1) * (Y - 1) # Check parity of Y to determine if numbers are in increasing or decreasing order if Y % 2 != 0: # Add X to the area if Yth row is odd add = X else: # Add 2*Y - X to the area if Yth row is even add = 2 * Y - X # Print the final result print(ans + add) # If X is greater than or equal to Y, implying Xth column is the outer boundary else: # Compute the area of the inner square ans = (X - 1) * (X - 1) # Check parity of X to determine if numbers are in increasing or decreasing order if X % 2 == 0: # Add Y to the area if Xth column is even add = Y else: # Add 2*X - Y to the area if Xth column is odd add = 2 * X - Y # Print the final result print(ans + add) # Driver Code Y = 2 X = 3 number_spiral(Y, X) 

using System; class GFG {  // Function to compute the value at position (Y, X) in the  // number spiral  static void NumberSpiral(long Y, long X)  {  // If Y is greater than X, implying Yth row is the outer  // boundary  if (Y > X)  {  // Compute the area of the inner square  long ans = (Y - 1) * (Y - 1);  long add = 0;  // Check parity of Y to determine if numbers are in  // increasing or decreasing order  if (Y % 2 != 0)  {  // Add X to the area if Yth row is odd  add = X;  }  else  {  // Add 2*Y - X to the area if Yth row is even  add = 2 * Y - X;  }  // Print the final result  Console.WriteLine(ans + add);  }  // If X is greater than or equal to Y, implying Xth  // column is the outer boundary  else  {  // Compute the area of the inner square  long ans = (X - 1) * (X - 1);  long add = 0;  // Check parity of X to determine if numbers are in  // increasing or decreasing order  if (X % 2 == 0)  {  // Add Y to the area if Xth column is even  add = Y;  }  else  {  // Add 2*X - Y to the area if Xth column is odd  add = 2 * X - Y;  }  // Print the final result  Console.WriteLine(ans + add);  }  }  // Driver Code  static void Main()  {  long Y = 2, X = 3;  NumberSpiral(Y, X);  } } 

// Function to compute the value at position (Y, X) in the number spiral function numberSpiral(Y, X) {  // If Y is greater than X, implying Yth row is the outer boundary  if (Y > X) {  // Compute the area of the inner square  let ans = (Y - 1) * (Y - 1);  let add = 0;  // Check parity of Y to determine if numbers are in increasing or decreasing order  if (Y % 2 !== 0) {  // Add X to the area if Yth row is odd  add = X;  } else {  // Add 2*Y - X to the area if Yth row is even  add = 2 * Y - X;  }  // Print the final result  console.log(ans + add);  }  // If X is greater than or equal to Y, implying Xth column is the outer boundary  else {  // Compute the area of the inner square  let ans = (X - 1) * (X - 1);  let add = 0;  // Check parity of X to determine if numbers are in increasing or decreasing order  if (X % 2 === 0) {  // Add Y to the area if Xth column is even  add = Y;  } else {  // Add 2*X - Y to the area if Xth column is odd  add = 2 * X - Y;  }  // Print the final result  console.log(ans + add);  } } // Driver Code let Y = 2, X = 3; numberSpiral(Y, X); 

8 

Time Complexity: O(1)
Auxiliary Space: O(1)