# Centered Square Numbers in Java

In this tutorial, we will understand how to check the number is a centered square number. It is one of the prevalent interview questions of IT companies. Firstly, we will understand the meaning of centered square numbers later we will create a java program for the same.

## Centered Square Numbers

Centered Square numbers are the figurate numbers

that are recursively described as:

Q(num) = Q(num - 1) + 4 x (num - 1), where num >= 1 and Q(0) = 1

Example:

For num = 1ry of Java

Q(1) = Q(1 - 1) + 4 x (1 - 1) => Q(1) = Q(0) + 4 x 0 = 1 + 0 = 1

For num = 2

Q(2) = Q(2 - 1) + 4 x (2 - 1) => Q(2) = Q(1) + 4 x 1 = 1 + 4 = 5

For num = 3

Q(3) = Q(3 - 1) + 4 x (3 - 1) => Q(3) = Q(2) + 4 x 2 = 5 + 8 = 13

For num = 4

Q(4) = Q(4 - 1) + 4 x (4 - 1) => Q(4) = Q(3) + 4 x 3 = 13 + 12 = 25

For num = 5

Q(5) = Q(5 - 1) + 4 x (5 - 1) => Q(5) = Q(4) + 4 x 4 = 25 + 16 = 41

### Implementation

Approach 1: Recursive

Let us now see a recursive java program to find the first fifteen centered square numbers.

``````public class CenteredSquareNumber
{
public int detectCenteredSqureNum(int n)
{
// dealing with the base case
if(n == 1)
{
return n;
}
// calculation of the central square number recursively
return detectCenteredSqureNum(n - 1) + 4 * (n - 1);
}
// beginning of the Main method
public static void main(String[] argvs)
{
// creation of an object of the class named CenteredSquareNumber
CenteredSquareNumber obj = new CenteredSquareNumber();
// calculation of 15 centered square numbers  from the beginning
int num = 15;
System.out.println("The first " + num + " Centered Square Number are: \n");
for(int j = 1; j <= 15; j++)
{
int res = obj.detectCenteredSqureNum(j);
System.out.print(res + " ");
}
}
}
``````

Output:

Explanation: The above program has space complexity = O(1).

The time complexity of the program O(t), where t is the tth position of the central square number that is to be found.

Approach 2: Iterative

The above program is optimized to reduce the complexities. Here, an array is used to store the result.

``````public class CenteredSquareNumber2
{
// Main method
public static void main(String[] argvs)
{
// calculating the initial 15 centered square numbers
int n = 15;
// creation of an array to store the calculated centered square number
int res[] = new int[n + 1];
System.out.println("The first " + n + " Centered Square Number are: \n");
for(int j = 1; j <= 15; j++)
{
// dealing with the base case
if(j == 1)
{
res[j] = 1;
}
else
{
res[j] = res[j - 1] + 4 * (j - 1);
}
// displaying the result
System.out.print(res[j] + " ");
}
}
}
``````

Output:

Explanation: The space complexity of the above program =  O(n). here, n is the total number of central squared numbers to be calculated. and the time complexity = O(1).

Approach 3:

This is another optimized approach.

``````public class CenteredSquareNumber3
{
// beginning of the main method
public static void main(String[] argvs)
{
// calculating the first 15 centered square numbers
int n = 15;
// A variable to store just the last computed centered square number
int lastCenSqrdNum = 0;
System.out.println("The first " + n + " Centered Square Number are: \n");
for(int j = 1; j <= 15; j++)
{
// dealing with the base case
if(j == 1)
{
lastCenSqrdNum = 1;
}
else
{
lastCenSqrdNum = lastCenSqrdNum + 4 * (j - 1);
}
// displaying the result
System.out.print(lastCenSqrdNum + " ");
}
}
}
``````

Output:

Explanation: The time complexity here = O(1). The space complexity also is O(1) as no arrays have been taken into account to store the resultant.

Approach 4: Mathematical formula

Q(num) = num2 + (num - 1)2, where num>= 1

Example:

For num = 1

Q(1) = 12 + (1 - 1)2 => Q(1) = 1 + 02 = 1 + 0 = 1

For num = 2

Q(2) = 22 + (2 - 1)2 => Q(2) = 4 + 12 = 4 + 1 = 5

``````public class CenteredSquareNumber4
{
// Beginning of the Main method
public static void main(String[] argvs)
{
// calculating the first 15 centered square numbers
int n = 15;
System.out.println("The first " + n + " Centered Square Number are: \n");
for(int j = 1; j <= 15; j++)
{
int res = (j * j) + ((j - 1) * (j - 1));
// displaying the result
System.out.print(res + " ");
}
}
}
``````

Output:

Explanation: The time complexity = O(1) .The space complexity = O(1).