Algocademy Logo

Course Outline

Print X in C++ with O(n^2) Time Complexity


Given a positive integer n print matrix containing an X as in the example below

Example:

Input: n = 5
Output:
x---x
-x-x-
--x--
-x-x-
x---x
Explanation:
Each line contains exactly n = 5 characters and two 'x's.
Each diagonal contains 'x'



Hints:

Notice that on each line there will be exactly two x and the other characters are all -. The only exception is the middle line which will have only one x. How can we use this info?

We can print the matrix line by line. For each line we need to know the two columns where we should print x. How can we know these two columns for every line?

We'll store the columns' indices in two variables firstX and secondX, initially equal to 1 and n respectively for the first line.
How should these variables change from line to line?

firstX should get incremented and secondX should get decremented.
Now for each line, you now the 'special' columns. How will you print that line?

We'll use a for loop to iterate through every column index from 1 to n.
What should we do inside the loop?

We should use an if - else statement and check if the current index is firstX or secondX and if so, print x. Otherwise, print -.

Understanding the Problem

The core challenge of this problem is to generate a matrix of size n x n where the diagonals are marked with 'x' and the rest of the elements are '-'. This problem is significant in understanding how to manipulate and generate patterns in a matrix, which is a common task in computer graphics, game development, and various algorithmic challenges.

Approach

To solve this problem, we can follow these steps:

  1. Initialize two variables, firstX and secondX, to keep track of the positions of 'x' in each row.
  2. Iterate through each row and update the positions of 'x' accordingly.
  3. For each row, construct the string by placing 'x' at the positions indicated by firstX and secondX and '-' elsewhere.
  4. Print the constructed string for each row.

Algorithm

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

  1. Initialize firstX to 0 and secondX to n-1.
  2. For each row from 0 to n-1:
    • Initialize an empty string line.
    • For each column from 0 to n-1:
      • If the column index is equal to firstX or secondX, append 'x' to line.
      • Otherwise, append '-' to line.
    • Print the line.
    • Increment firstX and decrement secondX.

Code Implementation

#include <iostream>
using namespace std;

void printX(int n) {
    int firstX = 0;
    int secondX = n - 1;

    for (int i = 0; i < n; ++i) {
        string line = "";
        for (int j = 0; j < n; ++j) {
            if (j == firstX || j == secondX) {
                line += 'x';
            } else {
                line += '-';
            }
        }
        cout << line << endl;
        firstX++;
        secondX--;
    }
}

int main() {
    int n;
    cout << "Enter the value of n: ";
    cin >> n;
    printX(n);
    return 0;
}

Complexity Analysis

The time complexity of this approach is O(n^2) because we have a nested loop where both the outer and inner loops run n times. The space complexity is O(1) if we do not consider the space used for the output.

Edge Cases

Some potential edge cases include:

  • n = 1: The output should be a single 'x'.
  • n = 2: The output should be: 
        xx
    xx

Testing

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

  • Simple cases like n = 1 and n = 2.
  • Odd and even values of n.
  • Large values of n to test the performance.

Thinking and Problem-Solving Tips

When approaching such problems, it is essential to:

  • Break down the problem into smaller, manageable parts.
  • Think about the pattern and how it can be generated programmatically.
  • Consider edge cases and how the solution can handle them.

Conclusion

In this blog post, we discussed how to generate a matrix containing an 'X' pattern given a positive integer n. We explored the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for developing strong problem-solving skills and algorithmic thinking.

Additional Resources

For further reading and practice problems related to this topic, consider the following resources: