# Count And Say Problem Solution

Count And Say Problem: The count-and-say sequence is a sequence of digit strings defined by the recursive formula:

• `countAndSay(1) = "1"`
• `countAndSay(n)` is the way you would “say” the digit string from `countAndSay(n-1)`, which is then converted into a different digit string.

To determine how you “say” a digit string, split it into the minimal number of substrings such that each substring contains exactly one unique digit. Then for each substring, say the number of digits, then say the digit. Finally, concatenate every said digit.

Example :

```Input: n = 4
Output: "1211"
Explanation:
countAndSay(1) = "1"
countAndSay(2) = say "1" = one 1 = "11"
countAndSay(3) = say "11" = two 1's = "21"
countAndSay(4) = say "21" = one 2 + one 1 = "12" + "11" = "1211"```

## Problem Solution In Python

``````class Solution(object):
def countAndSay(self, n):
s0 = '1'
for i in range(1, n):
s1, k = '', 1
for j in range(1, len(s0)):
if s0[j-1] == s0[j]: k += 1
else: s1, k = s1 + str(k) + s0[j-1], 1
s1 += str(k) + s0[-1]
s0 = s1
return s0
``````

## Problem Solution In Java

``````public String countAndSay(int n) {
if(n == 0) return "";
String res = "1";
for(int i = 1; i <n; i++){
String s = res;  res="";
int count = 1;// attention for the logic
char pre = s.charAt(0);
for(int j = 1; j < s.length(); j++){
if(s.charAt(j) == pre)
count++;
else{
res += count+""+pre;
pre = s.charAt(j);
count = 1;
}
}
res += count +""+ pre;
}
return String.valueOf(res);
}
``````

## Problem Solution In C++

``````class Solution {
public:
string countAndSay(int n) {
string temp="1";
string ans="";
if(n==1)return temp;
for(int i=2;i<=n;i++)
{
char value=temp;
int count=1;
ans="";
for(int j=1;j<temp.size();j++)
{
if(temp[j]==value)count++;
else
{
ans+=count+'0';
ans+=value;
count=1;
value=temp[j];
}
}
ans+=count+'0';
ans+=value;
temp=ans;
}
return ans;
}
};
``````

## Problem Solution In C

``````char* fromLast(char* last) {
char *s = last;
int count;
int index = 0;
char *result = (char*) malloc(2 * strlen(last));
while(*s != '\0') {
count = 1;
while(*s == *(s+1)) {
count++;
s++;
}
result[index++] = count + '0';
result[index++] = *(s);
s++;
}
result[index] = '\0';
return result;
}
char* countAndSay(int n) {
if(n == 1)
return "1";
return fromLast(countAndSay(n-1));
}``````