Magical Pattern

Easy
0/40
Average time to solve is 20m
23 upvotes
Asked in companies
Reliance Jio Infocomm LtdGoldman SachsCRED

Problem statement

You have been given an integer 'N'. Your task is to print the Magical Pattern(see examples) for the given 'N'.

Example :

For 'N' : 4
Pattern :
4 3 2 1 2 3 4                                                                   
3 3 2 1 2 3 3                                                                   
2 2 2 1 2 2 2                                                                   
1 1 1 1 1 1 1                                                                   
2 2 2 1 2 2 2                                                                   
3 3 2 1 2 3 3                                                                   
4 3 2 1 2 3 4
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first input line contains an integer 'T', the number of test cases. Then 'T' test cases follow.

The first and the only line of input contains the integer 'N'.
Output Format : 
For each test case print the Magical Pattern as shown in the example.
Note : 
You don't need to print anything. It has already been taken care of, just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N <= 10^2

Time Limit : 1 sec
Sample Input 1 :
1
3
Sample Output 1 :
3 2 1 2 3 
2 2 1 2 2  
1 1 1 1 1 
2 2 1 2 2 
3 2 1 2 3
Sample Input 2 :
1
5
Sample Output 2 :
5 4 3 2 1 2 3 4 5 
4 4 3 2 1 2 3 4 4 
3 3 3 2 1 2 3 3 3 
2 2 2 2 1 2 2 2 2 
1 1 1 1 1 1 1 1 1 
2 2 2 2 1 2 2 2 2 
3 3 3 2 1 2 3 3 3 
4 4 3 2 1 2 3 4 4 
5 4 3 2 1 2 3 4 5
Hint

Find the relation of each cell with i, j where i and j are row and column number of the cell respectively.

Approaches (1)
Brute Force

Think of all elements as having coordinates. The element in the center row and center column will have coordinates (0, 0). We will refer to it as the origin. The first coordinate measures the horizontal distance from the origin and the second one measures the vertical distance. The right and down directions are positive directions and consequently, the up and left directions are negative directions. So, the element just to the right of the origin will have coordinates (1, 0) and the element just above the origin will have coordinates (0, -1). 

 

Now, we can figure out that the coordinates of the elements at the top left, top right, bottom left and bottom right are (-(N - 1), -(N - 1)), (-(N - 1), (N - 1)), ((N - 1), -(N - 1)) and ((N - 1), (N - 1)) respectively.

 

Now that we got the coordinates for each element to be printed, we can start to look for the relationship between an element's value and its coordinates.

 

We can notice that if the coordinates of an element are (i, j) then its value is min(abs(i), abs(j)) + 1. So to print them, we can run two nested loops: both from -(N - 1) to (N - 1).

Time Complexity

O(N^2), where ‘N’ is the given integer.

 

We iterate from -(N - 1) to N over each element from -(N - 1) to N i.e. we iterate 2*N times over 2*N elements. Hence, the overall time complexity will be O(N^2).

Space Complexity

O(1).

 

We are using no extra space. Hence, the overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Magical Pattern
Full screen
Console