JavaScript Program to Generate Number Sequence
Find the n’th term in the Look-and-say (Or Count and Say) Sequence. The look-and-say sequence is the sequence of the below integers:
1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211
How is the above sequence generated?
n’th term is generated by reading (n-1)’th term.
The first term is "1"
Second term is "11", generated by reading first term as "One 1"
(There is one 1 in previous term)
Third term is "21", generated by reading second term as "Two 1"
Fourth term is "1211", generated by reading third term as "One 2 One 1"
and so on
How to find n’th term?
Example:
Input: n = 3
Output: 21
Input: n = 5
Output: 111221
Table of Content
- Using Iterative Approach
- Using Recursive Approach
Number sequence using Iterative Approach
In this approach, we iteratively generate each term of the sequence starting from the base case “1”. After which we maintain a current term and use it to generate the next term by counting consecutive digits. The process continues until we reach the nth term.
Example: The below code implements a JavaScript Program to generate a number sequence using an iterative approach.
function countAndSay(n) {
// Base case: the first term is always "1"
let result = "1";
// Iteratively generate each term starting from the second term
for (let i = 1; i < n; i++) {
let temp = "";
let count = 1;
// Iterate through each digit in the current term
for (let j = 1; j < result.length; j++) {
// If the current digit is the same as the
//previous one, increment the count
if (result[j] === result[j - 1]) {
count++;
} else {
temp += count + result[j - 1];
count = 1;
}
}
// Append the count and the last digit
temp += count + result[result.length - 1];
// Update the result to the newly generated term
result = temp;
}
// Return the nth term of the sequence
return result;
}
// Example usage
const n = 5;
console.log("The " + n + "th term of the Count and Say sequence is:
" + countAndSay(n));
Output
The 5th term of the Count and Say sequence is: 111221
Time Complexity: O(2^N)
Auxiliary Space: O(2^N)
Using Recursive Approach
In the recursive approach, we define a function to generate the nth term of the sequence based on the (n-1)th term. After which we recursively call this function to generate each term until we reach the base case. The base case is when n is 1, in which case we return “1” as the first term of the sequence.
Example: The below code implements a Program to generate a number sequence using a recursive approach.
function countAndSayRecursive(n) {
// Base case: the first term is always "1"
if (n === 1) {
return "1";
}
// Recursive call to generate the
// (n-1)th term of the sequence
const prev = countAndSayRecursive(n - 1);
let temp = "";
let count = 1;
// Iterate through each digit of the (n-1)th term
for (let i = 1; i < prev.length; i++) {
if (prev[i] === prev[i - 1]) {
count++;
} else {
temp += count + prev[i - 1];
count = 1;
}
}
// Append the count and the last digit to the temporary result
temp += count + prev[prev.length - 1];
// Return the newly generated term
return temp;
}
// Example usage
const n = 5;
console.log("The " + n +
"th term of the Count and Say sequence (recursive approach) is: "
+ countAndSayRecursive(n));
Output
The 5th term of the Count and Say sequence (recursive approach) is: 111221
Time Complexity: O(N*2^N)
Auxiliary Space: O(n)
Contact Us