Count And Say

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
32 upvotes
Asked in companies
FacebookAppleExpedia Group

Problem statement

Write as you speak is a special sequence of strings that starts with string “1” and after one iteration you rewrite the sequence as whatever you speak.

Example : 
The first few iterations of the sequence are :
First iteration: “1”
    As we are starting with one.

Second iteration: “11”
    We speak “1” as   “one 1” then we write it as “11”

Third iteration: “21”
    We speak “11” as “Two 1” then we write it as “21”

Fourth iteration: “1211”
    We speak “21” as “one 2, one 1”  then we write it as “1211”

Fifth iteration: “111221”
    We speak “1211” as “one 1, one 2, two 1” then we write it as “111221”

Sixth iteration: “312211”
    We speak “111221” as “three 1, two 2, one 1” then we write it as “312211”

You will be given a single positive integer N, Your task is to write the sequence after N iterations.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains a single positive integer T, denoting the number of test cases.

The first line of each test case contains a single integer N, denoting the number of iterations.
Output Format: 
For each query print the string that represents the sequence after the nth iteration.
Note: 
You don't have to print anything, it has already been taken care of. Just Implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 30

Time Limit: 1 sec
Sample Input 1 :
2
1
2
Sample Output 1:
1
11
Explanation For Sample Input 2:
First iteration: “1”
    As we are starting with one.

Second iteration: “11”
    We speak “1” as   “one 1” then we write it as “11”
Sample Input 2 :
2
3
4
Sample Output 2:
21
1211
Hint

Simulation

Approaches (1)
Simulation
  • The best way to solve this problem is to simulate it.
  • We will start our simulation with the single S. S will store the current sequence. At first, the S will be equal to “1”.
  • Then we will repeat the following steps for N-1 iterations.
    • Declare a temporary string Temp with an empty string. We will use Temp to store consecutively similar digits.
    • We will declare an array Count. We will store the count of the consecutively similar digits in count.
    • Now we will iterate through string S to build Temp and count.
      •  Let's say we are position i, we will count the consecutive frequency of S[i], and to do so we will keep on increasing the count of S[i] until all the digits are same, and once we get a new digit we will insert this digit in temp and initialize its count with one and will continue the same process.
        • For example, if we have string “1121”, then at the start we will insert ‘1’ into temp and initialize its count to 1 and as then we will move further again when we encounter a consecutive ‘1’ we will increment the counter to 2, and when we encounter ‘2’ in the string we will insert this into temp so temp becomes “12” and we will initialize its count to 1.
        • Now when we encounter 1 again it will be treated as a new character because the previous character was ‘2’ so we will insert this into temp and initialize its count to ‘1’, so finally, after complete traversal temp will be “121”, and count array will be [2,1,1],
  • We will append S[i] to Temp and store count of consecutive digits starting from i in Count
  • Now we have to build the sequence for the next iteration.
  • To do this we reset S with an empty string and iterate the Temp and Count array.
    • If we are currently at the ith index then add Count[i] to S and then add Temp[i] to S.
  • For example, we are having the sequence S as “1211” and we want to find a sequence for the next iteration then we will first traverse S and make the Temp and Count array which will look like this.
    • Temp[1] = 1 , Count[1] = 1
    • Temp[2] = 2 , Count[2] = 1
    • Temp[3] = 1 , Count[3] = 2
  • So the new sequence will be “111221”
Time Complexity

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

 

After each iteration, the size of the sequence is becoming approximately double.

Space Complexity

O(M), M is the size of the final sequence. 

 

Because we are storing the count of the digit in the count array and the digits in the Temp string.

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Count And Say
Full screen
Console