CODEWITHSUNDEEP
cstringalgorithm
Luv
Luv

Reputation: 5461

Find the nth count-and-say sequence element

Given a problem, 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.

I have made the solution as by scanning each string and generating next string accordingly It takes time as O(nm) where m is the length of the largest string and n is the number given

Here it the code

void countnsay(char str[][1000],int n)
{
int i=1,k;
int j=0;
while(i<=(n-1))
{
//scan str[i-1]
j=0;
k=0;        //for building the new string array 
while(j<strlen(str[i-1]) )
    {
    char c=str[i-1][j];
    int cnt=1;

    while(c==str[i-1][++j])
    cnt++;

    str[i][k++]=cnt+48;
    str[i][k++]=c;

    }
str[i][k]='\0';
i++;

}
printf("%s",str[n-1]);  
}




int main()
{
int n=5;
char str[1000][1000];
strcpy(str[0],"1");
countnsay(str,n);
return 0;
}

Could there be a more better solution to this problem? Please give some suggestions/hints. Thanx in advance

Upvotes: 4

Views: 4045

Answers (2)

Jaswanth Chowdary
Jaswanth Chowdary

Reputation: 1

def count_and_say(n):
    string= '1'
    for i in range(n-1):
        count = 1
        result = ''
        for j in range(len(string)):
            if j == len(string)-1 or string[j]!=string[j+1]:
                result += str(count)+string[j]
                count = 1
            else:
                count+=1
        string = result
    return string
n = int(input())
print(count_and_say(n))

Upvotes: -1

Luchian Grigore
Luchian Grigore

Reputation: 258618

You can use dynamic programming. After some time, you'll encounter already existing substrings which were already computed. You can keep a map of already computed sequences:

1 -> 11
11 -> 21

Now you need to compute 1211.

You first go for 1, which you already know is 11.

The you encounter 2. You don't have this, so compute 12 and add it to the map:

2 -> 12

The you encounter 11, which, again, you have in your map as 21.

Concatenate these and you get

111221

and the new map

1 -> 11
11 -> 21
2 -> 12

EDIT: You only look for consecutive identical numbers, so only keep those in the map.

Upvotes: 5

Related Questions