# Count And Say InterviewBit Solution

**Problem: **__Count And Say__

**Problem Description:**

The count-and-say sequence is the sequence of integers beginning as follows:

`1, 11, 21, 1211, 111221, ... `

`1 is read off as `**one ****1** or 11.
11 is read off as **two ****1****s** or 21.
21 is read off as **one ****2****,**** then one ****1** or 1211.

Given an integer n, generate the nth sequence.

*Note: The sequence of integers will be represented as a string.*

**Example:**

```
if n = 2,
the sequence is 11.
```

### Approach:

The approach is to use a simple brute force.

**For ****A**** ****=**** ****1****,** ans1 = "1" // Base case
**For ****A**** ****=**** ****2****,** start traversing ans, and keep count of the current character.
=> For the current case ans2 becomes "11" since the count of **"1"** in ans1 is **ONE**.
**For ****A**** ****=**** ****3****,** ans2 has **TWO**** ****"1"****,**** **so ans3 = "21"
**For ****A**** ****=**** ****4****,** in ans3 count of 2 is ONE, and count of 1 is ONE. So ans 4 becomes "1211"
**For ****A**** ****=**** ****5****,** in ans4 count of 1 is ONE, then 2 comes with count ONE, then again 1 comes with count TWO. So ans5 = "111221".

**Time & Space complexity:**

**Time Complexity****:**** ****O****(****N****)**

- As you have to traverse from 1 to N, and the string would never become too big because the maximum continuous character that can occur is only 3. You can try it on paper to find out.

**Space Complexity****:**** ****O****(****1****)**

- We are storing only two strings, the current one and the previous one. So the space is almost constant.

**Solution:**

Code in C++.