Count-and-Say
Last updated
Was this helpful?
Last updated
Was this helpful?
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 groups so that each group is a contiguous section all of the same character. Then for each group, say the number of characters, then say the character. To convert the saying into a digit string, replace the counts with a number and concatenate every saying.
For example, the saying and conversion for digit string "3322251":
Given a positive integer n, return the nth term of the count-and-say sequence.
Example:
We observe that in order to generate a member of the sequence from the precedent number, we read off the digits of the number while counting the number of digits pertaining the same group. We essentially try to replicate this process through our algorithm. The problem can become more simplified through a recursive implementation however this did not occur to me until having found an iterative solution. I've outline the iterative steps in the below.
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.
We first establish the case when the input n is 1 which we will immediately return 1
We want to do the same steps n - 1 number of times which explains the loop
We use a nested loop along a two pointer approach [i,j] in order to obtain the count of consecutive element e as well as store element e itself.
Since only j will move forward as long as the elements[i] & j are the same, j - i will represent the count. Since i hadn't moved, element[i] will be stored as the element that was being counted. We do so until i loops through the string
We then decrease n since we have to undertake the same steps n - 1 times
We then assign the count sequence string that we built thorugh the previous steps to s and we reinitialize i,j in order to perform the counting steps delineated above
Time: O(2**n) Space: O((2**n)-1)
Time complexity: The exponential time complexity stems from the worst scenario where any two adjacent digit in the sequence are not identical, then its next sequence would double the length, rather than having a reduced length. As a result, we could assume that in the worst case, the length of the sequence would grow exponentially.
Space complexity: Within each loop, we are using a container (res is the variable used as a container)to keep the result of the next sequence. The memory consumption of the container is proportional to the length of the sequence that the function needs to process.
The recursive implementation slighly reduces the code nonetheless we follow the same logic in the above. As we are going down the call stack in the recursion, we are at each step of the way building the sequence as well as decreasing n in order to stop our recursion thorugh our base case. When n == 1, the function goes to the base case and returns result which would be the sequence that would have been built corresponding to n. result then goes up the call stack until it ultimately gets returned to the main function in line 3.