Void of Diamond

Easy
0/40
5 upvotes

Problem statement

You are given an integer ‘N’, ‘N’ will always be an odd integer. Your task is to print a pattern with the following description:

1. The pattern will consist of ‘N’ lines.
2. The pattern will consist of ‘ ‘ (space) and ‘*’ characters only.
3. The pattern will be a “Void of Diamond” pattern.
4. A “Void of Diamond” pattern is a pattern ‘N’ * ‘N’ cells and ‘ ‘ characters make a diamond shape and ‘*’ fill all other points.
5. For a better understanding of the “Void of Diamond” pattern refer to example and sample input-output.

For example:

If ‘N’ is 5 then the pattern will be-

*****
** **
*   *
** **
*****
Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer 'T' representing the number of test cases.

Then each test case contains a single integer ‘N’ denoting the size of the pattern.

Output Format:

For each test case, print 'N' strings denoting the pattern.

The output of each test case will be printed in a separate line.

Constraints:

1 <= T <= 5
3 <= N <= 500

Where ‘T’ is the number of test cases, ‘N’  is the size of the pattern. ‘N’ will be odd for all test cases.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Sample Input 1:

2
5
3

Sample Output 1:

*****
** **
*   *
** **
*****
***
* *
***

Explanation of Sample Input 1:

Test Case 1:

Given ‘N’ = 5
We will print the pattern as the description of the “Void of Diamond” pattern.

Test Case 2:

Given ‘N’ = 3
There will be only 1 ‘ ‘ space in the diamond pattern.

Sample Input 2:

2
7
9

Sample Output 2:

*******
*** ***
**   **
*     *
**   **
*** ***
*******
*********
**** ****
***   ***
**     **
*       *
**     **
***   ***
**** ****
*********

Explanation of Sample Input 2:

Test Case 1:

Given ‘N' = 7
The pattern is printed such that ‘ ‘ making a diamond and ‘*’ filling other points.

Test Case 2:

Given ‘N’ = 9
Created a 9*9 grid and all space cells make a diamond pattern.
Hint

We can see the ‘N’ * ‘N’ grid as an x-y plane, and can easily divide it into 4 symmetric parts and is there any relation of ‘ ‘ characters with coordinates?

Approaches (1)
Pattern printing

The idea is here to visualize the problem in a different way, here ‘N’ will be odd so along the middle vertical line and middle horizontal this ‘N’ * ‘N’ grid can be divided into 4 symmetric parts and we can see it as an x-y plane. So we can see this ‘N’ * ‘N’ grid as a square on coordinate axis with the bottom left corner at { -((‘N’ - 1) / 2),  -((‘N’ - 1) / 2)} and upper right corner at { (‘N’ - 1) / 2 ,  (‘N’ - 1) / 2}.

Now if we assign coordinates to all other points as {x, y} we will find that in a quadrant all ‘ ‘ cells will form a triangular region and if we combined them all we will get a mathematical equation as |x| + |y| < (‘N’ - 1) / 2.

So now we run 2 loops for all coordinates and make a character ‘ ‘ if the sum of the absolute value of coordinates is less than ( ‘N’ - 1) / 2 otherwise it will be a ‘*’ character and here we can say in this case we will generate the pattern in a way such that first, we will generate the bottom line then will move till the top line but actually it won’t affect our pattern because it is symmetric with the horizontal bisector.

 

Algorithm:

 

  • Create an array of strings for storing the pattern say ‘answer’.
  • Run a loop from ‘i’ = -(‘N’ - 1)/2  to ‘i’ = (‘N’ -1)/2
  • Create a string ‘str’ for storing the current row of pattern.Run a loop from ‘j’ = -(‘N’ - 1) / 2  to ‘j’ = (‘N’ - 1) / 2.
  • If absolute(i) + absolute(j) is less than (‘N’ - 1) / 2 then append a ‘ ‘ character to the ‘str’, else append ‘*’ to the ‘str’.
  • Append ‘str’ to ‘answer’.

 

  • Return the ‘answer’ array that contains the pattern.
Time Complexity

O(N ^ 2), where N is the size of the pattern.

 

We are traversing each point of the ‘N’ * ‘N’ grid so we are doing ‘N’ ^ 2 iterations here so the overall time complexity is O(N ^ 2).

Space Complexity

O(N ^ 2), where N is the size of the pattern.

 

As we will be storing the result in an array of strings that contains ‘N’  strings of size ‘N’ so overall space complexity will be O(N ^ 2).

Code Solution
(100% EXP penalty)
Void of Diamond
Full screen
Console