Ninja and power of 2

Easy
0/40
Average time to solve is 15m
22 upvotes
Asked in companies
AmazonCognizantRadisys Corporation

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, the third row has 4 numbers, and so on.

Ninja starts placing numbers in increasing order, with absolute difference 1, starting from 1 and continuing till he encounters 9, and then he again restarts from 1.

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
23
4567
89123456
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 'N' lines denoting the required pattern.
Constraints: 
1 <= T <= 5
1 <= N <= 15
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
4
Sample Output 1 :
1
23
4567
1
23
4567
89123456
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 more than the previous value. So we place 2.Then we put 2 and move to the following line because this line will contain only 2 elements. In the following line, we have to place 4 numbers, so we place 4, 5, 6, and 7.
In the second test case, we are required to create a pattern consisting of 4 lines. First-line contains ‘1’. From the second line, we have to place a number one more than the previous value. So we place 2.Then we put 2 and 3 and move to the following line because this line will contain only 2 elements. In the following line, we have to place 4 numbers, so we place 4, 5, 6, and 7.In the last line, we have to place 8 numbers, so we place 8, 9, 1, 2, 3, 4, 5, and 6.
Sample Input 2 :
2
7
2
Sample Output 2 :
1
23
4567
89123456
7891234567891234
56789123456789123456789123456789
1234567891234567891234567891234567891234567891234567891234567891
1
23
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 final pattern.
  • We initialize a variable ‘k’ to 1, which will be the starting value for the pattern.
  • We will iterate over all the rows, i.e., i = 0 to N - 1:
  • We will run a for loop starting from 0 and less than 2 ^ i.
  • If k is less than 10, we will insert the value in the matrix ‘ans’.
  • Otherwise, we will reset the value of k to 1 and then insert the value in the matrix ‘ans’.
  • We will return the matrix ‘ans’ as the final answer.


 

Time Complexity

O(N*2^N), where N is the number of lines.


 

As 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 + 4 + … + 2^(N-1) * N = 2^N - 1, which is equivalent to O(N*2^N).


 

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

Space Complexity

O(N*2^N), where N is the number of lines.


 

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

Code Solution
(100% EXP penalty)
Ninja and power of 2
Full screen
Console