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 , generate the th sequence.

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

**Thoughts:**

This question is not hard. We can do a iteration through 1 to . Each time we look back and examine the th sequence, and count the number of different numbers appearing in it.

**Code (Java):**

public class Solution {
public String countAndSay(int n) {
String number = "1";
for(int i = 2; i <= n; ++i) {
String newNumber = new String();
for(int j = 0; j < number.length();) {
char current = number.charAt(j);
int count = 0;
while(j < number.length() &&
current == number.charAt(j)) {
count++;
j++;
}
newNumber += "" + count + current;
}
number = newNumber;
}
return number;
}
}

**Code (C++):**

class Solution {
public:
string countAndSay(int n) {
string number = "1";
for(int i = 2; i <= n; ++i) {
string newNumber;
for(int j = 0; j < number.size();) {
char current = number[j];
int count = 0;
while(current == number[j]) {
j++;
count++;
}
stringstream ss;
ss << count;
string temp;
ss >> temp;
newNumber += temp;
newNumber.push_back(current);
}
number = newNumber;
}
return number;
}
};

### Like this:

Like Loading...

*Related*

Ozan Tabak

Jan 05, 2013@ 08:06:39Use string builder in java to concenate Strings for better performance.

public class Solution {

public String countAndSay(int n) {

String str = “1”;

StringBuilder strBuilder = new StringBuilder();

for(int s = 0; s < n – 1; s++) {

int len = str.length();

strBuilder.setLength(0);

char lastChar = str.charAt(0);

int charCnt = 1;

for (int i = 1; i < len; i++) {

char currChar = str.charAt(i);

if (lastChar == currChar) {

charCnt++;

}

else {

strBuilder.append(charCnt).append(lastChar);

charCnt = 1;

}

lastChar = currChar;

}

strBuilder.append(charCnt).append(lastChar);

str = strBuilder.toString();

}

return str;

}

}