Print Rhombus in C++ with Time Complexity O(n)

Given an odd positive integer n print a rhombus of stars as in the example below

Example:

Input: n = 5
Output:
  *  
 *** 
*****
 *** 
  *  

Explanation:
There are n = 5 lines. Each line contains exactly n = 5 characters.
1st line contains two spaces, one '*' and two spaces.
2nd line contains one space, three '*' and one space.
3rd line contains five stars.
4th line contains one space, three '*' and one space.
5th line contains two spaces, one '*' and two spaces.

Note: Be careful to add the necessary spaces at the end of every line!

Understanding the Problem

The core challenge of this problem is to print a rhombus shape using stars ('*') and spaces (' '). The rhombus should be symmetric and centered, with the number of lines and characters per line equal to the given odd integer n. This problem is significant in learning how to manipulate loops and conditionals to create specific patterns, which is a common task in programming.

Approach

To solve this problem, we need to understand the pattern of spaces and stars for each line:

The middle line (n//2 + 1) has all stars and no spaces.
Lines above the middle line have increasing spaces and decreasing stars as we move upwards.
Lines below the middle line mirror the lines above it.

Naive Solution

A naive solution would involve manually calculating the number of spaces and stars for each line and printing them. However, this approach is not scalable and can be error-prone for larger values of n.

Optimized Solution

An optimized solution involves using loops to dynamically calculate the number of spaces and stars for each line. This approach is more efficient and easier to manage.

Algorithm

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

Loop through each line from 1 to n.
For each line, calculate the number of spaces and stars based on the line's position relative to the middle line.
Print the calculated number of spaces followed by the stars.

Code Implementation


#include <iostream>
using namespace std;

void printRhombus(int n) {
    int mid = n / 2;
    for (int i = 0; i < n; ++i) {
        int stars = n - 2 * abs(mid - i);
        int spaces = (n - stars) / 2;
        
        // Print leading spaces
        for (int j = 0; j < spaces; ++j) {
            cout << ' ';
        }
        
        // Print stars
        for (int j = 0; j < stars; ++j) {
            cout << '*';
        }
        
        // Print trailing spaces (optional, for alignment)
        for (int j = 0; j < spaces; ++j) {
            cout << ' ';
        }
        
        cout << endl;
    }
}

int main() {
    int n;
    cout << "Enter an odd positive integer: ";
    cin << n;
    if (n % 2 == 0) {
        cout << "Please enter an odd number." << endl;
    } else {
        printRhombus(n);
    }
    return 0;
}

Complexity Analysis

The time complexity of this solution is O(n) because we are iterating through each line once. 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 smallest odd positive integer.
Very large values of n: Ensure the program handles large inputs efficiently.

Testing

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

n = 1
n = 3
n = 5
n = 7
n = 101 (a large odd number)

Thinking and Problem-Solving Tips

When approaching such problems, it is helpful to:

Break down the problem into smaller parts.
Look for patterns and symmetries.
Use loops and conditionals effectively.
Practice similar pattern-printing problems to improve your skills.

Conclusion

In this blog post, we discussed how to print a rhombus of stars given an odd positive integer n. We explored the problem definition, approach, algorithm, and provided a detailed C++ implementation. Understanding and solving such problems is crucial for developing strong problem-solving skills in programming.

Additional Resources

For further reading and practice, consider the following resources: