Decagonal Numbers in Java

In this section, we will learn what is Decagonal number and also create Java programs to that calculates the Decagonal number. The Decagonal number program is frequently asked in Java coding interviews and academics.

Decagonal Number

A decagonal number is a figurate number, which is recursively defined as:

Thus,

D(1) = D(1 – 1) + 8 * 1 – 7 = D(0) + 8 – 7 = 0 + 8 – 7 = 0 + 1 = 1

D(2) = D(2 – 1) + 8 * 2 – 7 = D(1) + 16 – 7 = 1 + 16 – 7 = 1 + 9 = 10

D(3) = D(3 – 1) + 8 * 3 – 7 = D(2) + 24 – 7 = 10 + 24 – 7 = 10 + 17 = 27

D(4) = D(4 – 1) + 8 * 4 – 7 = D(3) + 32 – 7 = 27 + 32 – 7 = 27 + 25 = 52

D(5) = D(5 – 1) + 8 * 5 – 7 = D(4) + 40 – 7 = 52 + 40 – 7 = 52 + 33 = 85

Fined Decagonal Number

There are various approahes to find the decagonal number. In this section, we will discuss the following three approaches:

Uisng Recursion
Using Dynamic Programming
Using Mathematical Formula

Using Recursion

As we already know the recursive formula, it is easy to find the decagonal numbers using recursion. The following program shows the same.

FileName: DecagonalNumbers.java

  public class DecagonalNumbers   {  // a method that computes the nth Decagonal numbers  public int findDecagonalNum(int n)  {      // handling the base case      if(n == 0)      {          return 0;      }      // recursively computing the decagonal numbers      // using the recursion formula      return findDecagonalNum(n – 1) + 8 * n – 7;  }  // main method  public static void main(String[] argvs)  {  // creating an object of the class DecagonalNumbers  DecagonalNumbers obj = new DecagonalNumbers();  System.out.println(“The first 10 Decagonal numbers are: “);  int range = 10; // range upto which the decagonal numbers are computed  for(int i = 1; i <= range; i++)  {      int ans = obj.findDecagonalNum(i);      System.out.print(ans + ” “);  }  }  }  

Output:

The first 10 Decagonal numbers are:   1 10 27 52 85 126 175 232 297 370

Complexity Analysis: As the recursion goes from n to 0 for finding the decagonal numbers, therefore, the time complexity of the program is O(n), where n is the nth decagonal number. As the program is not using any extra space, therefore, the space complexity of the program is O(1).

The time complexity of the above program can be reduced further as we are computing the same subproblem again and again. For example, if we compute D(3), then recursively, D(3) gets reduced to D(2), which in turn gets reduced to D(1). Thus, we see that D(2) and D(1) are computed again, and this can be avoided. The following approach shows the same.

Using Dynamic Programming

We can use an auxiliary array for storing the computed decagonal numbers and can use them in further computation. Observe the following program.

FileName: DecagonalNumbers1.java

  public class DecagonalNumbers1  {  // main method  public static void main(String[] argvs)  {  // creating an object of the class DecagonalNumbers1  DecagonalNumbers1 obj = new DecagonalNumbers1();  System.out.println(“The first 10 Decagonal numbers are: “);  int range = 10; // range upto which the decagonal numbers are computed  int dp[] = new int[range + 1];  for(int i = 1; i <= 10; i++)  {      dp[i] = dp[i – 1] + 8 * i – 7;      System.out.print(dp[i] + ” “);  }  }  }  

Output:

The first 10 Decagonal numbers are:   1 10 27 52 85 126 175 232 297 370

Complexity Analysis: The time complexity of the program is O(1). As the program is using an Auxiliary array, therefore the space complexity of the program is O(range), where the range is the value up to which the decagonal numbers are computed.

If we observe the recursive formula, we find that the current decagonal number is dependent on the last computed decagonal number only and not on all of the previously computed decagonal numbers. Therefore, instead of an array, we can use a variable for storing the previously computed decagonal number. Observe the following program.

FileName: DecagonalNumbers2.java

  public class DecagonalNumbers2  {  // main method  public static void main(String[] argvs)  {  // creating an object of the class DecagonalNumbers2  DecagonalNumbers2 obj = new DecagonalNumbers2();  System.out.println(“The first 10 Decagonal numbers are: “);  int range = 10; // range upto which the decagonal numbers are computed  int prv = 0;  for(int i = 1; i <= 10; i++)  {      int curr = prv + 8 * i – 7;      prv = curr;      System.out.print(curr + ” “);  }  }  }  

Output:

The first 10 Decagonal numbers are:   1 10 27 52 85 126 175 232 297 370

Complexity Analysis: The time complexity of the program is O(1). As the program is not using any extra space, therefore the space complexity of the program is constant, i.e., O(1).

Using Mathematical Formula

The mathematical formula for computing the decagonal numbers are:

Thus,

D(1) = 1 x ((4 x 1) – 3) = 1 x (4 – 3) = 4 – 3 = 1

D(2) = 2 x ((4 x 2) – 3) = 2 x (8 – 3) = 2 x 5 = 10

D(3) = 3 x ((4 x 3) – 3) = 3 x (12 – 3) = 3 x 9 = 27

D(4) = 4 x ((4 x 4) – 3) = 4 x (16 – 3) = 4 x 13 = 52

D(5) = 5 x ((4 x 5) – 3) = 5 x (20 – 3) = 5 x 17 = 85

Implementation

Observe the implementation of the above mathematical formula.

FileName: DecagonalNumbers3.java

  public class DecagonalNumbers3  {  // main method  public static void main(String[] argvs)  {  // creating an object of the class DecagonalNumbers3  DecagonalNumbers3 obj = new DecagonalNumbers3();  System.out.println(“The first 10 Decagonal numbers are: “);  int range = 10; // range upto which the decagonal numbers are computed  int dp[] = new int[range + 1];  for(int i = 1; i <= 10; i++)  {      // using the mathematical formula      int num = i * (4 * i – 3);      System.out.print(num + ” “);  }  }  }  

Output:

The first 10 Decagonal numbers are:   1 10 27 52 85 126 175 232 297 370

Complexity Analysis: The time complexity of the program is O(1).

Next TopicJava Binary to Hexadecimal Conversion

Decagonal Numbers in Java

Decagonal Numbers in Java

Decagonal Number

Fined Decagonal Number

Using Recursion

Using Dynamic Programming

Using Mathematical Formula

Implementation

Convert List to Array in Java

Java Garbage Collection

You may also like