Table of contents

Introduction

Fibonacci Half Pyramid: Problem statement

2.1.

Example

2.2.

Input

2.3.

Output

2.4.

Explanation

2.5.

Approach

C solution

3.1.

Code

3.2.

Output

C++ solution

4.1.

Code

4.2.

Output

Java Solution

5.1.

Code

5.2.

Output

Python Solution

6.1.

Code

6.2.

Output

Complexity

7.1.

Time Complexity

7.2.

Space Complexity

FAQs

Key Takeaways

Last Updated: Mar 27, 2024

Fibonacci Half Pyramid

Author Gaurav Budhiraja

Do you think IIT Guwahati certified course can help you in your career?

Yes

Introduction

Programmers are often encountered with a problem that is made up of mixing two or more concepts, and a good programmer knows how to approach the solution step by step. There is no need to come up with the most optimal solution in one go. We should first take time to build a general solution powered up by our first intuition.

No worries if you got stuck thinking about the solution for the Fibonacci half pyramid; remember, you either succeed or you learn. Today, we will learn about the Fibonacci half pyramid and discuss the approach to solving the problem in four different programming languages, i.e., C, C++, Java, and Python.

Fibonacci Half Pyramid: Problem statement

Given the 'n' number, representing the n-number of rows (starting with row number 1), we need to construct an n-row half triangle such that the triangle elements follow the Fibonacci Series in Python and the number of elements in a row is equal to the current row number.

Example

Let's look at an example.

Input

n = 3

Output

1  			// Row number 1
1 2  		// Row number 2
3 5 8  		// Row number 3

Explanation

We start the Fibonacci series with 1 in the first row. Because the number of elements in row 1 equals 1, we move to the following line. Similarly, in row 2, when we get to the next two elements of the series, we move to row number 3.

This pattern continues until the number of rows printed equals the user input of required rows.

Approach

Step 1: We will define initial variables for the 1st and 2nd elements of the series, 0 and 1.

Step 2: We will then take the input from the user, i.e., N.

Step 3: We will iterate through the 1st loop, N number of times starting from 1.

Step 4: We will nest another loop inside, which will loop from 1 to the outer loop variable.

Step 5: In the inner loop, we will update the third variable as the sum of precious two and edit the first variable's value as the second's and the second's variable value as the third's, i.e., (c = a+b, a = b, b = c).

Step 6: We will print the third variable as the last line of the inner loop.

Step 7: We will print a new line character out of the inner loop.

Now, let us discuss the above approach's code to solve the Fibonacci half pyramid problem in different languages.

C solution

Fibonacci half pyramid can be constructed in C programming language as given below:

Code

int main()
{
    int outer, inner, a = 0, b = 1, c = a + b;
    printf("Enter the number of rows: ");
    int n_rows;
    scanf("%d", &n_rows);
    for (outer = 1; outer <= n_rows; outer++)
    {
        for (inner = 1; inner <= outer; inner++)
        {
            printf("%d ", c);

            c = a + b;
            a = b;
            b = c;
        }
        printf("\n");
    }
    return 0;
}

You can also try this code with Online C Compiler

Run Code

Output

Enter the number of rows: 5

1 
1 2 
3 5 8 
13 21 34 55 
89 144 233 377 610

C++ solution

Fibonacci half pyramid can be constructed in C++ programming language as given below:

Code

#include <iostream>
using namespace std;

int main()
{
    int outer, inner, a = 0, b = 1, c = a + b;
    cout<<"Enter the number of rows: ";
    int n_rows;
    cin>>n_rows;
    for (outer = 1; outer <= n_rows; outer++)
    {
        for (inner = 1; inner <= outer; inner++)
        {
            cout<<c<<" ";
            c = a + b;
            a = b;
            b = c;
        }
        cout<<endl;
    }
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Enter the number of rows: 4

1 
1 2 
3 5 8 
13 21 34 55

If you are starting out with C++, our guided path for C++ will help you get a head start over others!

Java Solution

Fibonacci half pyramid can be constructed in Java programming language as given below:

Code

import java.util.Scanner;
public class FibonacciHalfPyramid {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the number of rows: ");
        int outer, inner, a = 0, b = 1, c = a + b;
        int n_rows = sc.nextInt();
        for (outer = 1; outer <= n_rows; outer++) {
            for (inner = 1; inner <= outer; inner++) {

                System.out.print(c + " ");
                c = a + b;
                a = b;
                b = c;
            }
            System.out.println();
        }
        sc.close();
    }
}

You can also try this code with Online Java Compiler

Run Code

Output

Enter the number of rows: 6

1 
1 2 
3 5 8 
13 21 34 55 
89 144 233 377 610 
987 1597 2584 4181 6765 10946

If you are starting out with Java, our guided path for Java will help you get a head start over others!

Python Solution

Fibonacci half pyramid can be constructed in Python programming language as given below:

Code

n_rows = int(input("Enter the number of rows: "))
a = 0
b = 1
c = a+b
for outer in range(1, n_rows+1):
    for inner in range(1, outer+1):
        print(c, end=" ")
        c = a+b
        a = b
        b = c
    print("\r")

You can also try this code with Online Python Compiler

Run Code

Output

Enter the number of rows: 4

1 
1 2 
3 5 8 
13 21 34 55

If you are starting out with python, our guided path for python will help you get a head start over others!

Complexity

Let's discuss the time and space complexity of the above approach.

Time Complexity

Since the logic and approach is the same, the time complexity of the solution in all the languages remains the same, i.e., O(n²) for using two nested loops ranging from 1 to n, where n is the number of rows.

Space Complexity

Since the logic and approach is the same, and no extra space is used, the space complexity of the solution in all the languages also remains the same, i.e., O(1).

Must Read Fibonacci Series in JavaScript

FAQs

What are pattern problems?
Pattern programs are simply patterns of integers, alphabets, or symbols in a specific order. The for loop condition may be used to solve these pattern programs quickly.
What is the difference between the pascal triangle and the Fibonacci half triangle?
The binomial coefficients are arranged in a triangular array in pascal's triangle. In contrast, the Fibonacci half triangle is an arrangement of the Fibonacci series in the form of a triangle.
Why do we need to practice pattern problems?
The easiest way to learn how looping structures in general-purpose programming languages function is to use pattern programs. It aids newcomers in visualizing how each loop iteration works. This question is frequently asked during campus placements and employment interviews.
How can we approach this problem using dynamic programming?
We can tabulate the data with the bottom-up approach for the Fibonacci series using an array instead of directly calculating them in the inner loop.

Key Takeaways

This article extensively discussed the famous pattern problem of constructing the Fibonacci half triangle in C, C++, Java, and Python with illustrative examples. We want you to solve these types of problems or even more difficult ones next time, for which we have curated a unique path for you to take your problem-solving skills to the next level.