Number Pattern

Easy
0/40
Average time to solve is 15m
profile
Contributed by
15 upvotes
Asked in companies
HSBCDell TechnologiesAmazon

Problem statement

Ninja wants to build a number pattern.

Example For ‘N’ = 4 

Pattern:

4444
3444
2344
1234

Your task is to make a program that prints a similar pattern for a given 'N'.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer 'T' which denotes the number of test cases or queries to be run.

The first line of each test case contains one integer, ‘N’, denoting the number of rows.
Output Format: 
For each test case print, 'N' strings denoting the pattern.

The output of each test case will be printed on a separate line.
Note: 
You do not need to input or print anything, as it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 5
1 <= N <= 200

Time Limit: 1 sec
Sample Input 1:
2
5
2
Sample Output 1:
55555
45555
34555
23455
12345
22
12
Explanation of Sample Input 1:
Test case 1:

In the first test case, as ‘N’ is equal to ‘5’, We will have to print five lines. We have a print a square-like pattern where the upper right triangle along with the main diagonal will be filled with the input number and the lower-left triangle will be a triangle wherein each row, number of elements increases from ‘1’ to ‘N’ - 1;

Test case 2:

In the second test case, as ‘N’ is equal to ‘2’, We will have to print two lines.
Sample Input 2:
2
1
4
Sample Output 2:
1
4444
3444
2344
1234
Explanation of Sample Input 2:
Test case 1:
As ‘N’ is equal to ‘1’, we just need to print one line i.e 1.
Hint

Derive the next row from the previous one.

Approaches (1)
String Manupilation

We can see that our left-bottom triangle is a pattern of an increasing number and the right upper pattern is a constant pattern. Hence we can first compute a string appending ‘N’ to a local string ‘N’ - 1 time. These will be later used for making the upper-right triangle. Now, we can compute the left-bottom triangle running a while loop with decreasing ‘N’ where we will append ‘N’ to a local string and putting this string in an array of strings. Once, these computations are done, we will join our right triangle with the left triangle by iterating through the array of strings and append the required substring from the precomputed string. While appending, as we are dealing with strings where one number in string format has many digits, we need to know the number of digits present in our original ‘N’ to remove one whole number from the substring.

 

Algorithm:

 

  • Declare an array ‘arr’ of string type to store the pattern.
  • Declare a string ‘preComp’
    • Run a loop from ‘i’ = ‘0’ to ‘N’ - 1
      • Append ‘N’ to ‘preComp’
  • Declare a variable ‘numberOfDigits’ that will contain the number of digits present in ‘N’.
  • Declare an empty string ‘temp’
  • Run a while loop which will terminate when ‘N’ reaches 0
    • Update ‘temp’ by adding the current value of ‘N’ before it.
    • Put temp into the array ‘arr’
    • Decrease ‘N’ by 1
  • Declare a variable ‘x’ that will contain the size of the string preComp
  • Run a loop through the array arr
    • Update arr by adding a substring of ‘preComp’ of size ‘x’ from the starting point.
    • Decrease ‘x’ by ‘numberOfDigits’
  • Return the array ‘arr’.

 

Time Complexity

O(N ^ 2) where N is the given input.

We are precomputing our triangles using ‘N’ iterations. For each row, we are calculating a substring that requires O(N), Hence the overall time complexity is O(N ^ 2).

Space Complexity

O(N ^ 2)  where N is the number of rows of the array

As we are returning an array of size “N” containing “N string” each of size ‘N’

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