# Count And Say

Posted: 12 Jan, 2021

Difficulty: Easy

#### 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.

##### 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
```

Approach 1

- 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.
- 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],

- Declare a temporary string
- 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”

SIMILAR PROBLEMS

# Ninja's Frustrating Homework

Posted: 8 Jul, 2021

Difficulty: Ninja

# Find All Subsets

Posted: 23 Jul, 2021

Difficulty: Easy

# Longest Common Prefix

Posted: 24 Jul, 2021

Difficulty: Moderate

# Hotel Rooms

Posted: 29 Jul, 2021

Difficulty: Moderate

# Subset OR

Posted: 31 Jul, 2021

Difficulty: Moderate