Diamond of numbers

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
13 upvotes
Asked in company
Samsung R&D Institute

Problem statement

Students at Ninja School were bored with their daily routine and wanted to try something new. So, they thought about observing patterns. While observing the patterns, they found a very interesting pattern which they wished to explore. Your task is to help the students to visualize the pattern for any given ‘N’.

Given an integer ‘N’ you need to return the corresponding pattern for it.

For example, pattern for N = 15 will be : 
          1 
         123 
        12345 
       1234567 
      123456789 
     12345678912 
    1234567891234 
   123456789123456 
    1234567891234 
     12345678912 
      123456789 
       1234567 
        12345 
         123 
          1
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.
The first and the only line of each test case contains a single integer 'N' denoting the number of rows.
Output format : 
For each test case return the corresponding pattern in the next ‘N’ lines.
Note : 
You are not required to print anything, it has already been taken care of. Just implement the function.
Constraints : 
1 <= T <= 10    
1 <= N <= 500

Time Limit : 1 sec
Sample Input 1 :
2
7
4
Sample Output 1 :
   1
  123
 12345
1234567
 12345
  123
   1
  1
 123
12345
 123
  1
Sample Input 2 :
2
5
6
Sample Output 2 :
  1
 123
12345
 123
  1
   1
  123
 12345
1234567
 12345
  123
   1
Hint

On observing the pattern of first (N/2 +1) rows and last (N/2) rows, can you think of a solution from those observations? 

Approaches (1)
Ad-hoc

In this pattern, each row starts with 1 and also ends with 1 and it is a diamond pattern so every row contains odd items.
 

Algorithm :

 

  1. Declare the 2-D vector ‘VECT’ and push N empty vectors in it.
  2. Initialize variable ‘COUNT’ to (N/2 + 1), variable ‘I’ to 0, and variable ‘M’ to ‘I’.
  3. Iterate from 1 to COUNT (say, iterator = ‘i’).
    1. Iterate from 1 to (‘COUNT’ - ‘i’) (say, iterator = ‘j’).
    2. Push space (“ ”) in the 2-D vector.
    3. Initialize ‘TEMP’ to ‘1’.
    4. Iterate from 1 to ( 2 * i - 1 ) (say, iterator = ‘k’).
      1. Push the value of ‘TEMP’ in ‘VECT’.
      2. Increment ‘TEMP’ by 1.
      3. If the value of ‘TEMP’ equals ‘ : ’ , then , initialize ‘TEMP’ to ‘1’.
      4. Increment the ‘M’.
  4. Iterate from (‘COUNT’-1) to 1 (say, iterator = ‘i’).
    1. Iterate from (‘COUNT’ - 1) to ‘i’  (say, iterator = ‘j’).
      1. Push space (“ ”) in the ‘VECT’.
      2. Initialize ‘TEMP’ to ‘1’.
      3. Iterate from 1 to ( 2 *i  - 1 ) (say, iterator = ‘k’).
      4. Push the value of ‘TEMP’ in the ‘VECT’.
      5. Increment ‘TEMP’ by 1.
      6. If the value of ‘TEMP’ equals ‘ : ’ , then , initialize ‘TEMP’ to ‘1’.
      7. Increment the ‘M’.
  5. Return ‘VECT’.
Time Complexity

O(N^2), where ‘N’ is the number of rows.

 

As we are returning every character of each line one at a time. The upper half diamond contains characters from N/2 to ‘N’ and the lower half diamond contains characters from ‘N’ to N/2. Hence the time required to print ‘N’ lines is N * (N+1)/2, which is equivalent to O(N^2).

Space Complexity

O(1)

 

Constant extra space is used

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