Print Triangle of Stars in Java (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 understanding how to control output formatting in Java. It is a common exercise in introductory programming courses to help students grasp the concept of nested loops.

Potential pitfalls include off-by-one errors, where the number of stars printed does not match the line number, and incorrect loop boundaries.

Approach

To solve this problem, we can use a simple loop structure. The naive approach involves using a single loop to iterate from 1 to n and printing the corresponding number of stars for each iteration. This approach is already optimal for this problem since it has a linear time complexity of O(n).

Naive Solution

The naive solution involves a single loop that runs from 1 to n. For each iteration, we print the current line number of stars. This approach is straightforward and efficient for this problem.

Optimized Solution

Since the naive solution is already optimal with a time complexity of O(n), there is no need for further optimization. However, we can ensure that our implementation is clean and follows best practices.

Algorithm

The algorithm can be broken down into the following steps:

Initialize a loop that runs from 1 to n.
For each iteration i, print i stars followed by a newline.

Code Implementation

public class TriangleOfStars {
    public static void main(String[] args) {
        int n = 5; // Example input
        printTriangleOfStars(n);
    }

    /**
     * Prints a triangle of stars with n lines.
     * @param n the number of lines in the triangle
     */
    public static void printTriangleOfStars(int n) {
        // Loop through each line
        for (int i = 1; i <= n; i++) {
            // Print i stars for the ith line
            for (int j = 1; j <= i; j++) {
                System.out.print("*");
            }
            // Move to the next line
            System.out.println();
        }
    }
}

Complexity Analysis

The time complexity of this solution is O(n) because we have a single loop that runs from 1 to n. The space complexity is O(1) as we are not using any additional data structures that grow with the input size.

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: Since the problem specifies a positive integer, negative values are invalid inputs.

Our algorithm handles these cases by ensuring the loop runs from 1 to n, and since n is assumed to be positive, we do not need to handle negative values explicitly.

Testing

To test the solution comprehensively, we can use a variety of 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.

We can use a simple main method to run these test cases and verify the output manually.

Thinking and Problem-Solving Tips

When approaching such problems, it is essential to:

Understand the problem requirements and constraints thoroughly.
Break down the problem into smaller, manageable steps.
Start with a simple solution and then look for potential optimizations.
Test the solution with various inputs, including edge cases.

Practicing similar problems and studying different algorithms can help improve 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.

We encourage readers to practice similar problems and explore further to enhance their understanding and proficiency in coding.

Additional Resources

For further reading and practice, consider the following resources: