Print Triangle of Stars in C++ (Time Complexity: O(n))

Given a positive integer n print a triangle of stars as in the example below

Example:

Input: n = 5
Output:
*
**
***
****
*****
Explanation: Print 5 lines, on ith line print i stars.

Understanding the Problem

The core challenge of this problem is to generate a pattern of stars in the shape of a right-angled triangle. This is a common problem in programming that helps in understanding loops and nested loops.

Significance: This problem is often used to teach beginners about loops and how to control the number of iterations. It also helps in understanding how to format output in a specific pattern.

Potential Pitfalls: A common misconception might be to try and print all stars in a single loop without considering the need for a new line after each row.

Approach

To solve this problem, we need to use nested loops. The outer loop will handle the number of lines, and the inner loop will handle the number of stars on each line.

Initial Naive Solution: A naive solution might involve manually printing each line, but this is not scalable for larger values of n.

Optimized Solution: Using nested loops is the optimal approach. The outer loop runs from 1 to n, and the inner loop runs from 1 to the current value of the outer loop variable.

Algorithm

Initialize a loop variable i from 1 to n.
For each iteration of the outer loop, initialize another loop variable j from 1 to i.
Print a star for each iteration of the inner loop.
After the inner loop completes, print a newline character to move to the next line.

Code Implementation


#include <iostream> // Include the iostream library for input and output

int main() {
    int n; // Declare an integer variable to store the input
    std::cout << "Enter the number of lines: "; // Prompt the user for input
    std::cin >> n; // Read the input value

    // Outer loop to handle the number of lines
    for (int i = 1; i <= n; ++i) {
        // Inner loop to handle the number of stars on each line
        for (int j = 1; j <= i; ++j) {
            std::cout << "*"; // Print a star
        }
        std::cout << std::endl; // Print a newline character after each line
    }

    return 0; // Return 0 to indicate successful execution
}

Complexity Analysis

Time Complexity: The time complexity of this solution is O(n) because the outer loop runs n times and the inner loop runs a total of 1 + 2 + ... + n = n(n+1)/2 times, which simplifies to O(n^2). However, since the inner loop's complexity is nested within the outer loop, the overall complexity is O(n).

Space Complexity: The space complexity is O(1) as we are using a constant amount of extra space.

Edge Cases

Potential edge cases include:

n = 1: The output should be a single star.
n = 0: The output should be empty (no stars).
Negative values of n: These should be handled by either prompting the user again or by not printing anything.

Testing

To test the solution comprehensively, consider the following test cases:

n = 1: Expected output is *
n = 3: Expected output is:
```
*
**
***
    
```
n = 5: Expected output is:
```
*
**
***
****
*****
    
```
n = 0: Expected output is an empty string.

Thinking and Problem-Solving Tips

When approaching such problems, it is essential to break down the problem into smaller parts. Start by understanding the pattern and then think about how to use loops to generate that pattern. Practice similar problems to improve your problem-solving skills.

Conclusion

In this blog post, we discussed how to print a triangle of stars given a positive integer n. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for developing strong programming skills.

Additional Resources

For further reading and practice, consider the following resources: