Hogben Numbers in Java

In this section, we will discover what the Hogben number is and develop Java programs that compute it. Java coding interviews and academic exams typically involve questions about the Hogben number program.

Hogben Number

The numbers that are recursively defined as follows are the Hogben numbers.

Where n >= 1 and H(0) = 1, H(n) = H(n-1) + 2 * (n-1)

Thus,

H(1) = H(1 - 1) + 2 * (1 - 1) = H(0) + 2 * 0 = 1 + 0 = 1

H(2) = H(2 - 1) + 2 * (2 - 1) = H(1) + 2 * 1 = 1 + 2 = 3

H(3) = H(3 - 1) + 2 * (3 - 1) = H(2) + 2 * 2 = 3 + 4 = 7

H(4) = H(4 - 1) + 2 * (4 - 1) = H(3) + 2 * 3 = 7 + 6 = 13

H(5) = H(5 - 1) + 2 * (5 - 1) = H(4) + 2 * 4 = 13 + 8 = 21

Let's examine the many methods for obtaining the Hogben numbers.

Recursive Approach

Let's look at how to find the first 10 Hogben numbers using a recursive method.

FileName: HogNum.java

public class HogNum   
{  
public int findHogNum(int n)  
{  
// handling the base case  
if(n == 1)  
{  
    return 1;   
}  
// recursively finding the nth Hogben number  
return (findHogNum(n - 1) + 2 * (n - 1));  
}  
  
// main method  
public static void main(String argvs[])  
{  
int n = 10;  
// creating an object of the class HogbenNum  
HogNum obj = new HogNum();  
System.out.println("The first " + n + " Hogben numbers are:");  
for (int j = 1; j <= n; j++)  
{  
int ans = obj.findHogNum(j);  
System.out.print(ans + " ");  
}  
}  
}  

Output

Complexity Analysis

The time complexity of the code is O(n), where n is the nth number, according to complexity analysis. The program has constant space complexity, or O (1).

Iterative Approach

Take a look at the iterative method for obtaining the first 10 Hogben numbers.

FileName: HogNum1.java

public class Hognum1  
{  
// main method  
public static void main(String argvs[])  
{  
int n = 10;  
// auxiliary array for storing the Hogben numbers  
int dp[] = new int[n + 1];  
dp[0] = 1;  
System.out.println("The first " + n + " Hogben numbers are:");  
for (int j = 1; j <= n; j++)  
{  
// computing the Hogben numbers  
dp[j] = dp[j - 1] + 2 * (j - 1);  
System.out.print(dp[j] + " ");  
}  
}  
}  

Output

Complexity Analysis

The program's time complexity is O (1). The program's space complexity is O(n), where n is the total number of Hogben numbers that need to be calculated.

The value of the most recent Hogben number computation is the single factor affecting the current Hogben number. Therefore, we are limited to using a variable to calculate the Hogben numbers rather than an array. See the code below.

FileName: HogNum2.java

public class HogNum2  
{  
// main method  
public static void main(String argvs[])  
{  
int n = 10;  
int temp = 1;  
System.out.println("The first " + n + " Hogben numbers are:");  
  
for (int j = 1; j <= n; j++)  
{  
// computing the Hogben numbers  
temp = temp + 2 * ( j - 1);  
System.out.print(temp + " ");  
}  
}  
}  

Output

Complexity Analysis

The program's time and space complexity are both O (1).

Using Mathematical Formula

The Hogben numbers are calculated using the following mathematical formula:

Where n >= 1, H(n) = n^2 - n + 1

Thus,

H(1) = 1^2 - 1 + 1 = 1 - 1 + 1 = 1

H(2) = 2^2 - 2 + 1 = 4 - 2 + 1 = 3

H(3) = 3^2 - 3 + 1 = 9 - 3 + 1 = 7

H(4) = 4^2- 4 + 1 = 16 - 4 + 1 = 13

H(5) = 5^2 - 5 + 1 = 25 - 5 + 1 = 21

The mathematical formula described above is used in the following code.

FileName: HogNum3.java

public class HogNum3  
{  
// main method  
public static void main(String argvs[])  
{  
int n = 10;  
  
System.out.println("The first " + n + " Hogben numbers are:");  
  
for (int j = 1; j <= n; j++)  
{  
// computing the Hogben numbers  
int ans = (j * j) - j + 1;  
System.out.print(ans + " ");  
}  
}  
}  

Output

Complexity Analysis

The program's time and space complexity are both O (1).