Count And Say Solution for Cognizant
Company: Cognizant · Difficulty: Easy · Topics: String, Recursion
Problem Statement
The count-and-say sequence is a sequence of digit strings defined by the recursive formula.
Examples
Example 1:
Input: n = 1
Output: "1"
Example 2:
Input: n = 4
Output: "1211"
Explanation:
countAndSay(1) = "1"
countAndSay(2) = say "1" = one 1 = "11"
countAndSay(3) = say "11" = two 1s = "21"
countAndSay(4) = say "21" = one 2 + one 1 = "12" + "11" = "1211"
Approach
Use recursion to build the sequence step by step, counting consecutive digits.
Time and Space Complexity
- Time Complexity: O(n * 2^n)
- Space Complexity: O(2^n)