C/C++ Coding Exercise – Count and Say – LeetCode Online Judge – Simulation of Number Sequences

The sequence is interesting. It starts from ‘1’. The next number always counts the previous number in digits one by one. For example, the second number in the series counts ‘1’ as One-‘1′, which is ’11’. And the third number counts second number ’11’ as Two-‘1′, which is ’21’.. and this goes on.

You are required to output the n-th number in the series. The original problem is from Leetcode Online Judge, so you can submit your solutions [here].

The input parameter is type of int and the return type should be string because the number may be too large to hold using a int.

If you understand the process of generating these numbers, you will have the ‘naive’ approach, which seems efficient enough. I don’t see any formula of generating the n-th number. To iterative the sequences from the first number seems the ‘best’ approach.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

class Solution {
public:
    string countAndSay(int n) {
        string a = "1";
        string b = a;
        for (int i = 1; i < n; i ++) {
            b = "";
            // current digit
            char c = a[0];
            // how many times this appear
            int cnt = 1;
            int len = a.length();
            for (int j = 1; j < len; j ++) {
                if (a[j] == c) {
                    cnt ++; 
                } else { // we have a new digit
                    string tmp = "";
                    // convert cnt to string
                    while (cnt) {
                        tmp = char(48 + (cnt % 10)) + tmp;
                        cnt /= 10;
                    }
                    // add previous digit
                    b = b + tmp + c;
                    // make current digit next
                    c = a[j];
                    cnt = 1;
                }
            }
            string tmp = "";
            // convert cnt to string
            while (cnt) {
                tmp = char(48 + (cnt % 10)) + tmp;
                cnt /= 10;
            }
            b = b + tmp + c;
            // iterative 
            a = b; 
        }
        return b;
    }
};

class Solution {
public:
    string countAndSay(int n) {
        string a = "1";
        string b = a;
        for (int i = 1; i < n; i ++) {
            b = "";
            // current digit
            char c = a[0];
            // how many times this appear
            int cnt = 1;
            int len = a.length();
            for (int j = 1; j < len; j ++) {
                if (a[j] == c) {
                    cnt ++; 
                } else { // we have a new digit
                    string tmp = "";
                    // convert cnt to string
                    while (cnt) {
                        tmp = char(48 + (cnt % 10)) + tmp;
                        cnt /= 10;
                    }
                    // add previous digit
                    b = b + tmp + c;
                    // make current digit next
                    c = a[j];
                    cnt = 1;
                }
            }
            string tmp = "";
            // convert cnt to string
            while (cnt) {
                tmp = char(48 + (cnt % 10)) + tmp;
                cnt /= 10;
            }
            b = b + tmp + c;
            // iterative 
            a = b; 
        }
        return b;
    }
};

The C++ string overloads the plus operator so it is convenient to concatenate strings. The bracket operator [] helps you easily to get the character from a string by using index.

The counter may be larger than 10, therefore we use the following to convert numbers to string.

1
2
3
4
5
6

string tmp = "";
// convert cnt to string
while (cnt) {
    tmp = char(48 + (cnt % 10)) + tmp;
    cnt /= 10;
}

string tmp = "";
// convert cnt to string
while (cnt) {
    tmp = char(48 + (cnt % 10)) + tmp;
    cnt /= 10;
}

However, the test cases here are not strong enough, because even simply tmp = char(48 + cnt) passes all test cases (the counter is less than 10). In other words, the numbers grow rapidly in this series. For example, when input is 25, you will have this big number:

13211321322113311213212312311211131122211213211331121321123123211231131122211211
13122113111231133221121321132122311211131122211213211321322112312321123113213221
12311311222113111231133221121113122113121113221112131221123113111231121123222112
13211321322113311213212312311211131211131221223113112221131112311332211211131221
13121113221112131221123113111231121123222112111312211312111322212321121113121112
13111213211231132132211211131221232112111312212221121123222112132113213221133112
13212312311211131122211213211321322113221321132132211231131122211331121321232221
12111312211312112213211231132132211211131221131211322113321132211221121332211231
13112221131112311332111213122112311311123112111331121113122112132113121113222112
31131122111213122112311311222112111331121113112221121113122113121113222112132113
21322123211211131211121332211231131122211311122122111312211213211312111322211231
13112221131112311332211211133112111311222112111312211311123113322112111312211312
11132221232112111312111213322112132113213221133112132123123112111311222112132113
21223112111311222112111312211312113221133221121113122113221321132132211231131122
21131112311311121321122112132231121113122113322113111221131221

–EOF (The Ultimate Computing & Technology Blog) —