(Count and Say)

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.

Thoughts:
This question is not hard. We can do a iteration through 1 to n. Each time we look back and examine the (n-1)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;
    }
};
Advertisements

1 Comment (+add yours?)

  1. Ozan Tabak
    Jan 05, 2013 @ 08:06:39

    Use 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;
    }
    }

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: