Decagonal Numbers in Java
This section explains what is a decagonal number and how to write Java programmes that compute decagonal numbers. Both academics and Java programmer interviews regularly question about the Decagonal number program.
The Decagonal Number
An example of a figurate number is a decagonal number, which is defined as follows:
D(m) = D(m - 1) + 8 * m – 7 Where m >= 1 and D(0) = 0
The Fined Decagonal Number
The decagonal number can be found using a variety of methods. The following three strategies will be covered in this section:
- Using the Recursion
- Using the Dynamic Programming
- Using the Mathematical Formula
Using the Recursion
Given that we are already familiar with the recursive formula, finding the decagonal numbers by recursion is simple. The same can be seen in the program below.
DecagonalNumbersDemo.java
public class DecagonalNumbersDemo
{
// a procedure for calculating its nth Decagonal number
public int findTheDecagonalNumber(int n)
{
// addressing the default case
if(m == 0)
{
return 0;
}
// the decagonal numbers are calculated iteratively
// utilising the formula for recursion
return findTheDecagonalNumber(m - 1) + 8 * m - 7;
}
// It is the main method
public static void main(String[] argvs)
{
// constructing a DecagonalNumbersDemo object
DecagonalNumbersDemo srj = new DecagonalNumbersDemo();
System.out.println("Here are the first ten decagonal numbers: ");
int range = 10; // r range that is used to calculate decagonal numbers
for(int s = 1; s <= range; s++)
{
int res = srj.findTheDecagonalNumber(i);
System.out.print(res + " ");
}
}
}
Output:
Here are the first ten decagonal numbers:
1 10 27 52 85 126 175 232 297 370
Analysis of Complexity: The temporal complexity of the programme equals O(n), wherein n is now the nth decagonal number, as the recursion used to get the decagonal numbers goes from n to 0 in this case. The program's space complexity is O(1) because it is not utilising any more space.
Given that we are repeatedly computing the same subproblem, the preceding program's temporal complexity can be decreased even further. In the case of computing D(3), for instance, D(3) is lowered to D(2), which is then reduced to D. (1). We can prevent this from happening by not having to recalculate D(2) and D(1). The same can be seen in the next method.
Using the dynamic programming
The obtained decagonal numbers can be stored in such an extra array for use in subsequent computations. Take note of the program below.
DecagonalNumbersDemo1.java
public class DecagonalNumbersDemo1
{
// It is the main method
public static void main(String[] argvs)
{
// constructing a DecagonalNumbersDemo1 object
DecagonalNumbersDemo1 srj = new DecagonalNumbersDemo1();
System.out.println("Here are the first ten decagonal numbers: ");
int range = 10; // range that is used to calculate decagonal numbers
int dpi[] = new int[range + 1];
for(int s = 1; s <= 10; s++)
{
dpi[s] = dpi[s - 1] + 8 * i - 7;
System.out.print(dpi[s] + " ");
}
}
}
Output:
Here are the first ten decagonal numbers:
1 10 27 52 85 126 175 232 297 370
Analysis of Complexity: The program's temporal complexity is O (1). Where ranging is the figure upto from which the decagonal values are computed, and because the programme uses an auxiliary array, its space complexity is O(range).
If we look now at recursive formula, we can see that the decagonal number that is being computed at the moment depends only on the decagonal number that was computed just before it, not on all of the decagonal numbers that have been computed before. Consequently, we can employ a variable to store the achieved by comparing decagonal number rather than an array. Take note of the programme below.
Using the Mathematical Formula
The decagonal values are calculated using the following mathematical formula:
D(m) = m x ((4 x m) - 3). In which m >= 1
Let's see how to apply the mathematical formula.
DecagonalNumbersDemo3.java
public class DecagonalNumbersDemo3
{
// It is the main method
public static void main(String[] argvs)
{
// constructing a DecagonalNumbersDemo3 object
DecagonalNumbersDemo3 srj = new DecagonalNumbersDemo3();
System.out.println("Here are the first ten decagonal numbers: ");
int range = 10; // range that is used to calculate decagonal numbers
int dpi[] = new int[range + 1];
for(int s = 1; s <= 10; s++)
{
// mathematical formula is used
int numb = s * (4 * s - 3);
System.out.print(numb + " ");
}
}
}
Output:
Here are the first ten decagonal numbers:
1 10 27 52 85 126 175 232 297 370