top of page

### Looking to master object-oriented and system design for tech interviews or career growth?

• Improve your system design and machine coding skills.

• Study with our helpful resources.

**We're in beta mode and would love to hear your feedback.

Search

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

Code in C++.

Tags:

bottom of page