Geek-onacci Number in C++

The Geek-onacci Number is a variation of the Fibonacci sequence, often introduced as a programming challenge. In this sequence, the first three terms are provided, and each subsequent term is calculated as the sum of the three preceding terms. It allows for exploring recursion, iteration, and dynamic programming concepts.

Explanation:

Initial Terms: The first three numbers of the Geek-onacci sequence are given explicitly, typically as input. Let's call these numbers G1, G2, and G3.

Recurrence Relation: For any number Gn in the sequence where n>3, it is calculated as:

• G(n)=G(n−1)+G(n−2)+G(n−3)

This means each term is the sum of the three terms before it.

Example: Suppose the first three terms are:

• G1=1
• G2=2
• G3=3

The sequence will be:

• G4=G3+G2+G1=3+2+1=6
• G5=G4+G3+G2=6+3+2=11
• G6=G5+G4+G3=11+6+3=20

Approach 1: Simple Approach

Program:

Output:

Enter G1, G2, G3: 1 2 3 
Enter the value of N: 5
The 5th Geek-onacci number is: 11   

Explanation:

1. Purpose of the Code

• The goal of the code is to calculate the Geek-onacci number at a specific position N in the sequence. The Geek-onacci sequence is a variation of Fibonacci, where every number is the sum of the last three numbers.

2. Input Explanation

The program takes four inputs:

• The first three terms of the sequence: G1, G2, and G3.
• The position N for which we want to find the Geek-onacci number.

3. Handle Simple Cases First

The program checks if N is 1, 2, or 3:

• If N=1, the result is G1 (the first term).
• If N=2, the result is G2 (the second term).
• If N=3, the result is G3 (the third term).

This is because these terms are already given as input and don’t need to be calculated.

4. Iterative Calculation for N>3

If N is greater than 3, the program uses a loop to calculate the terms from the 4th position up to N.

Steps in the Loop:

Initialize the First Three Terms:

• The program keeps track of the last three terms using variables term1, term2, and term3, which are initially set to G1, G2, and G3.

Calculate the Next Term:

• For each position i (starting from 4), the next term in the sequence is calculated as:
• current=term1+term2+term3
• This adds the last three terms to get the next term.

Shift the Terms:

After calculating the new term, the program updates the values of the last three terms:

• term1 is replaced by term2.
• term2 is replaced by term3.
• term3 is replaced by current (the newly calculated term).
• This ensures the program always has the latest three terms for the next calculation.

Repeat Until N:

• The loop continues until it calculates the term at position N.

Output the Result

Once the loop finishes, the value of term3 contains the Geek-onacci number at position N. The program then prints this result.

6. Example Walkthrough

Let’s go through an example where G1=1, G2=2, G3=3, and N=6.

Initial terms: term1 = 1, term2 = 2, term3 = 3.

Start the loop from i=4:

Step 1: current=1+2+3=6

• Update: term1 = 2, term2 = 3, term3 = 6.

Step 2: current=2+3+6=11

• Update: term1 = 3, term2 = 6, term3 = 11.

Step 3: current=3+6+11=20

• Update: term1 = 6, term2 = 11, term3 = 20.

After the loop, term3 = 20 is the Geek-onacci number at position N=6.

Complexity Analysis:

Time Complexity

The time complexity of the program is O(N).

• The program iterates from position 4 to N, calculating one term at a time.
• Each iteration involves a constant amount of work (a simple addition of three numbers and variable updates).
• Therefore, the number of operations is proportional to N.

Space Complexity

The space complexity of the program is O(1).

• The program uses only a fixed number of variables (term1, term2, term3, and current) to calculate the Geek-onacci numbers.
• It does not require any extra space like an array or recursion stack.
• Regardless of the value of N, the space usage remains constant.

Approach 2: Dynamic Programming with a Sliding Window Technique

This method stores the last three terms in an array and updates them iteratively. While similar to the previous approach, it structures the calculation differently for clarity and modularity.

Program:

Output:

Enter G1, G2, G3: 1 2 3
Enter the value of N: 6
The 6th Geek-onacci number is: 20   

Explanation:

1. Purpose of the Code

This program calculates the Geek-onacci number at position N. The Geek-onacci sequence is similar to the Fibonacci sequence but uses the sum of the last three numbers to calculate the next number.

2. Inputs to the Program

The program asks for four inputs:

• G1: The first term of the sequence.
• G2: The second term of the sequence.
• G3: The third term of the sequence.
• N: The position in the sequence for which the Geek-onacci number is needed.

3. Handling Simple Cases First

If N is 1, 2, or 3, the answer is directly one of the initial terms:

• If N=1, the result is G1.
• If N=2, the result is G2.
• If N=3, the result is G3.

The program returns these values without performing any further calculations since these terms are already provided.

4. Using an Array to Store Terms

For positions greater than 3, the program uses an array called terms of size 3:

• This array holds the last three numbers of the sequence.
• Initially, it is set as:
• terms[0] = G1
• terms[1] = G2
• terms[2] = G3

5. Loop to Calculate Terms

The program calculates all terms from 4 to N using a loop:

1. Compute the Next Term:
   • The next term in the sequence is the sum of the three numbers in the array: current=terms[0]+terms[1]+terms[2]
2. Shift the Array Values:
   • The array is updated to include the new term:
   • terms[0] (oldest term) is replaced by terms[1].
   • terms[1] (middle term) is replaced by terms[2].
   • terms[2] (newest term) is replaced by current.
   • This process ensures that the array always contains the latest three terms.
3. Repeat Until N:
   • The loop continues until the program calculates the Geek-onacci number at position N.

6. Return the Result

• After the loop ends, the value of terms[2] contains the Geek-onacci number at position N. This value is then printed as the result.

7. Example Walkthrough

Let’s go through an example where:

• G1=1, G2=2, G3=3, and N=6.

Initial State:

terms = [1, 2, 3].

Loop Calculations:

• For i=4:
• current=1+2+3=6.
• Update terms: [2, 3, 6].
• For i=5:
• current=2+3+6=11.
• Update terms: [3, 6, 11].
• For i=6:
• current=3+6+11=20.
• Update terms: [6, 11, 20].

Final Result:

• After the loop, terms[2] = 20, which is the 6th Geek-onacci number.

Complexity Analysis:

Time Complexity

• The program calculates the Geek-onacci numbers from the 4th position to the Nth position using a single loop.
• Each iteration performs a constant amount of work (adding three numbers and updating the array).
• Therefore, the total number of operations is proportional to N, resulting in a time complexity of O(N).

Space Complexity

• The program uses an array of fixed size (3 elements) to store the last three terms of the sequence.
• No additional memory is used, regardless of the size of N.
• As the array size remains constant, the space complexity is O(1), indicating constant space usage.