Game of Numbers

Easy
0/40
Average time to solve is 20m
26 upvotes
Asked in companies
HCL TechnologiesSamsung

Problem statement

Ninja loves playing with numbers. So one day, he wants to arrange a few numbers in the ‘N’ number of rows. The first row contains 1 number, the second row has two numbers, and so on.

On row 1, he places ‘1’. From the second row, he puts a number equal to one less than the number of the row at two ends of the row and places zeros in between.

You are given an integer ‘N’ denoting the given number of rows. Can you print the pattern Ninja wants to create?

Pattern for N = 4:

1
11
202
3003
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains ‘T’, denoting the number of test cases.

Each test case contains a single integer ‘N’, denoting the number of rows.
Output Format: 
For each test case, print a string denoting the required pattern in the following ‘N’ lines.
Constraints: 
1 <= T <= 10
1 <= N <= 10^2
Where ‘T’ denotes number of test cases and ‘N’ is the given integer denoting the given number of rows.

Time Limit: 1 sec
Sample Input 1 :
2
3
1
Sample Output 1 :
1
11
202
1
Explanation for Sample Input 1 :
In the first test case, we are required to create a pattern consisting of 3 lines. First-line contains ‘1’. From the second line, we have to place a number one less than the row number at two ends of the row and place zeros in between. So we place ‘1’ at two ends, and since the second line contains only two numbers, so there will be no ‘0’.In the third line, we have to place  ‘2’, because row number is 3 and one number less than that is ‘2’, at two ends. This line will have 3 digits, so we have to place one ‘0’ between the 2 ‘2’.
In the second test case, we are required to create a pattern consisting of 1 line. The first and only line will have ‘1’.
Sample Input 2 :
2
8
2
Sample Output 2 :
1
11
202
3003
40004
500005
6000006
70000007
1
11
Hint

 Can you print one line at a time? 

Approaches (1)
Brute Force

The key here is to traverse all the lines sequentially, and for each line, we print the required character at the given index.

The steps are as follows:

  • We define an ‘ans’ matrix to store the pattern.
  • We insert ‘1’ in the ‘ans’ matrix.
  • We run a for loop with the condition i is starting from 1 and is less than the number of rows, i.e., n:
  • For row value equal to i and col value equal to i or 0 we insert i in ‘ans’.
  • We run a for loop starting from 1 and less than i.
  • We insert ‘0’ in ‘ans’.
  • Finally, we return ‘ans’.
Time Complexity

O(N^2), where N denotes the number of lines in the pattern.

 

Here we are printing every character of each line one at a time. The first line contains one character, the second line two, and so on. Hence the time required to print N lines is 1 + 2 + 3 + … + N = (N*(N+1))/2, which is equivalent to O(N^2)

Hence the overall time complexity is O(N^2).



 

Space Complexity

O(N^2), where N denotes the number of lines in the pattern.

 

We are using a matrix, to store the pattern. Hence, the overall space complexity is O(N^2).

Code Solution
(100% EXP penalty)
Game of Numbers
Full screen
Console