Print Triangle of Stars in Python (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. The number of lines in the triangle is determined by the input integer n. Each line i contains exactly i stars.

This problem is significant in learning basic loops and string manipulation in Python. It is commonly used in introductory programming courses to teach control structures and iteration.

Potential pitfalls include off-by-one errors and incorrect loop boundaries.

Approach

To solve this problem, we can use a simple loop to iterate from 1 to n. For each iteration, we print a line containing the current iteration number of stars.

Let's discuss a naive solution and then an optimized one:

Naive Solution

The naive solution involves using a loop to print each line of stars. This approach is straightforward and works well for this problem.

Optimized Solution

Given the simplicity of the problem, the naive solution is already optimal. The time complexity is O(n) because we are iterating through the loop n times, and the space complexity is O(1) as we are not using any additional data structures.

Algorithm

Here is a step-by-step breakdown of the algorithm:

Start a loop from 1 to n (inclusive).
In each iteration, print a string of stars with a length equal to the current iteration number.

Code Implementation

def print_triangle_of_stars(n):
    # Loop from 1 to n (inclusive)
    for i in range(1, n + 1):
        # Print i stars
        print('*' * i)

# Example usage
n = 5
print_triangle_of_stars(n)

Complexity Analysis

The time complexity of this solution is O(n) because we have a single loop that runs n times. The space complexity is O(1) as we are not using any additional data structures.

Edge Cases

Potential edge cases include:

n = 1: The function should print a single star.
n = 0: The function should not print anything.
Negative values of n: The function should handle this gracefully, possibly by not printing anything.

Testing

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

n = 5: Should print 5 lines with increasing stars.
n = 1: Should print a single star.
n = 0: Should not print anything.
n = -3: Should not print anything.

Thinking and Problem-Solving Tips

When approaching such problems, it is helpful to:

Break down the problem into smaller parts.
Write out the expected output for a few sample inputs.
Use loops and string manipulation techniques effectively.
Test your solution with various edge cases.

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.

Practice is key to mastering these concepts. Try solving similar problems to improve your problem-solving abilities.

Additional Resources

For further reading and practice, consider the following resources: