Galaxy of stars

Easy
0/40
Average time to solve is 15m
profile
Contributed by
8 upvotes
Asked in company
Tata Consultancy Services (TCS)

Problem statement

Ninja wants to build a star pattern for a given odd number.

The pattern for ‘N’ = 7  will look like this:

*
**
***
****
***
**
*

Your task is that for a given odd integer 'N', print the pattern.

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 <= 99

Time Limit: 1 sec
Sample Input 1:
2
3
5
Sample Output 1:
*
**
*
*
**
***
**
*
Explanation of Sample Input 1:
Test case 1:

In the first test case of sample input 1, we need to print a triangle-like pattern wherein each line, the number of stars will be increasing till the central row and then it starts decreasing. So for n=3, till 2nd-row stars increase and then start decreasing.
Sample Input 2:
1
1
Sample Output 2:
*
Explanation of Sample Input 2:
Test case 1:
As ‘N’ is equal to ‘1’, we just need to print one line.
Hint

Observe the row number carefully.

Approaches (1)
String Manupilation

Here we can Initialising precompute a string of size (n + 1) / 2. For each row using the substring function, we can extract the number of stars needed and put them in an array of strings. We can run a loop where till the central row, we will increase the number of stars. We can keep a counter variable that will be increasing till the central row and decrease henceforth. Using this variable, we can calculate how many stars are required to be taken from the precomputed string. 

 

Algorithm:

 

  • Declare an array arr of string type and resize it with n
  • Declare a string ‘preComp’ where we shall precompute and store the stars
  • Run a loop from 'i' = 0 to (n+1)/2 and append stars to pre_comp
  • Declare a counter variable to count the number of stars in each row
  • Run a loop from 'i' = 1 to n
    • If i is less than equal to (n + 1) / 2.
      • Assign arr[i-1] with a substring of ‘preComp’ starting from 0th index and of size equal to counter variable.
      • Increment counter variable by 1
      • If i is equal to (n + 1) / 2, then the counter has already been increased by an extra unit. So we need to decrease it by 1
    • Else we need to decrease the counter variable first and then assign arr[i - 1] with a substring of ‘preComp’ starting from the 0-th index and of size equal to counter variable.
  • Return the array of string.

 

Time Complexity

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

We are traversing ‘N’ rows in each test case. In each row, we are finding substring of a string that takes O(N) time complexity. Hence the overall time complexity is O(N ^ 2).

Space Complexity

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

 

As we are returning an array of size ‘N’ containing ‘N string”’ each of size beginning from ‘1’ to ‘(N+1)/2’ and then decreasing back to ‘1.
 

Code Solution
(100% EXP penalty)
Galaxy of stars
Full screen
Console