Count and Say Problem in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Count and Say for n=4

What is the output of the Count and Say sequence for n=4?

DSA Typescript

function countAndSay(n: number): string {
  if (n === 1) return "1";
  const prev = countAndSay(n - 1);
  let result = "";
  let count = 1;
  for (let i = 1; i <= prev.length; i++) {
    if (prev[i] === prev[i - 1]) {
      count++;
    } else {
      result += count.toString() + prev[i - 1];
      count = 1;
    }
  }
  return result;
}
console.log(countAndSay(4));

A "312211"

B "1211"

C "111221"

D "21"

💡 Hint

Remember the sequence starts with "1" and each term describes the previous term.

The sequence starts as: 1, 11, 21, 1211. For n=4, the output is "1211".

🧠 Conceptual

intermediate

Understanding the Count and Say sequence

Which of the following best describes how the Count and Say sequence is generated?

A Each term is the count of digits followed by the digit itself from the previous term.

B Each term is the sum of digits from the previous term.

C Each term is the reverse of the previous term.

D Each term is the previous term repeated twice.

💡 Hint

Think about how you describe the digits in the previous term.

The sequence describes the count of digits followed by the digit itself from the previous term.

🔧 Debug

advanced

Identify the error in Count and Say implementation

What error will this code produce when calling countAndSay(3)?

DSA Typescript

function countAndSay(n: number): string {
  if (n === 1) return "1";
  const prev = countAndSay(n - 1);
  let result = "";
  let count = 1;
  for (let i = 0; i < prev.length; i++) {
    if (prev[i] === prev[i + 1]) {
      count++;
    } else {
      result += count.toString() + prev[i];
      count = 1;
    }
  }
  return result;
}
console.log(countAndSay(3));

A Infinite loop occurs

B Throws a TypeError due to undefined index access

C Runs correctly and outputs "21"

D Outputs "1211" incorrectly

💡 Hint

Check how the loop handles the last character.

The loop safely accesses prev[i + 1] which is undefined at the end, but comparison prev[i] === undefined is false, so it ends correctly.

❓ Predict Output

advanced

Output of Count and Say for n=5

What is the output of the Count and Say sequence for n=5?

DSA Typescript

function countAndSay(n: number): string {
  if (n === 1) return "1";
  const prev = countAndSay(n - 1);
  let result = "";
  let count = 1;
  for (let i = 1; i <= prev.length; i++) {
    if (prev[i] === prev[i - 1]) {
      count++;
    } else {
      result += count.toString() + prev[i - 1];
      count = 1;
    }
  }
  return result;
}
console.log(countAndSay(5));

A "111221"

B "312211"

C "1211"

D "211"

💡 Hint

Build the sequence step by step from n=1 to n=5.

The sequence is: 1, 11, 21, 1211, 111221 for n=5.

🚀 Application

expert

Count and Say sequence length for large n

What is the length of the Count and Say sequence string for n=6?

DSA Typescript

function countAndSay(n: number): string {
  if (n === 1) return "1";
  const prev = countAndSay(n - 1);
  let result = "";
  let count = 1;
  for (let i = 1; i <= prev.length; i++) {
    if (prev[i] === prev[i - 1]) {
      count++;
    } else {
      result += count.toString() + prev[i - 1];
      count = 1;
    }
  }
  return result;
}
const output = countAndSay(6);
console.log(output.length);

A 6

B 12

C 10

D 8

💡 Hint

Calculate the sequence up to n=6 and count the characters.

The sequence for n=6 is "312211" which has length 6.

Practice

1. What does the "Count and Say" sequence describe in simple terms?

easy

A. It describes each term by counting and saying the digits of the previous term.

B. It sorts the digits of the previous term in ascending order.

C. It adds the digits of the previous term to get the next term.

D. It reverses the digits of the previous term to form the next term.

Solution

1. Step 1: Understand the sequence definition

   The "Count and Say" sequence generates each term by describing the count of digits seen in the previous term.

2. Step 2: Compare options with definition

   Only It describes each term by counting and saying the digits of the previous term. correctly states this process; others describe unrelated operations.

3. Final Answer:

   It describes each term by counting and saying the digits of the previous term. -> Option A

4. Quick Check:

   Count and Say = Describe digits count [OK]

Hint: Remember: count digits, then say them aloud [OK]

Common Mistakes:

• Thinking it sorts digits instead of counting
• Assuming it sums digits for next term
• Confusing with reversing digits

2. Which of the following TypeScript function signatures correctly represents a function that takes a number n and returns the nth term of the Count and Say sequence as a string?

easy

A. function countAndSay(n: number): string

B. function countAndSay(n: string): number

C. function countAndSay(): number

D. function countAndSay(n: number): number[]

Solution

1. Step 1: Identify input and output types

   The function should take a number n (term index) and return a string representing that term.

2. Step 2: Match signature with requirements

   function countAndSay(n: number): string matches input as number and output as string; others mismatch types or parameters.

3. Final Answer:

   function countAndSay(n: number): string -> Option A

4. Quick Check:

   Input number, output string [OK]

Hint: Input is term number, output is sequence string [OK]

Common Mistakes:

• Using wrong input type (string instead of number)
• Returning number or array instead of string
• Missing input parameter

3. What is the output of the following TypeScript code snippet?

function countAndSay(n: number): string {
  if (n === 1) return "1";
  const prev = countAndSay(n - 1);
  let result = "";
  let count = 1;
  for (let i = 1; i <= prev.length; i++) {
    if (prev[i] === prev[i - 1]) {
      count++;
    } else {
      result += count + prev[i - 1];
      count = 1;
    }
  }
  return result;
}
console.log(countAndSay(4));

medium

A. "21"

B. "111221"

C. "312211"

D. "1211"

Solution

1. Step 1: Trace recursive calls and terms

   Term 1: "1"; Term 2: "11" (one 1); Term 3: "21" (two 1s); Term 4: "1211" (one 2, one 1).

2. Step 2: Confirm output for n=4

   The code returns "1211" for n=4, matching "1211".

3. Final Answer:

   "1211" -> Option D

4. Quick Check:

   Term 4 = "1211" [OK]

Hint: Remember sequence: 1, 11, 21, 1211... [OK]

Common Mistakes:

• Confusing term 3 and 4 outputs
• Off-by-one errors in loop
• Miscounting repeated digits

4. Identify the bug in this TypeScript implementation of the Count and Say sequence:

function countAndSay(n: number): string {
  if (n === 1) return "1";
  const prev = countAndSay(n - 1);
  let result = "";
  let count = 1;
  for (let i = 0; i < prev.length; i++) {
    if (prev[i] === prev[i + 1]) {
      count++;
    } else {
      result += count + prev[i];
      count = 1;
    }
  }
  return result;
}

medium

A. The count variable is not reset correctly inside the loop.

B. The loop should start from i = 1, not 0.

C. Accessing prev[i + 1] causes out-of-bounds error on last iteration.

D. The base case should return "0" instead of "1".

Solution

1. Step 1: Analyze loop boundary and indexing

   The loop runs from i=0 to prev.length-1, but accesses prev[i+1], which is undefined at last index.

2. Step 2: Identify error cause

   Accessing prev[i+1] at last iteration causes out-of-bounds access, leading to incorrect behavior or runtime error.

3. Final Answer:

   Accessing prev[i + 1] causes out-of-bounds error on last iteration. -> Option C

4. Quick Check:

   Check array bounds when accessing i+1 [OK]

Hint: Check array access at last index carefully [OK]

Common Mistakes:

• Ignoring last element boundary
• Starting loop at wrong index
• Incorrect base case value

5. Given the Count and Say sequence, what is the 6th term generated by the following TypeScript function?

function countAndSay(n: number): string {
  if (n === 1) return "1";
  const prev = countAndSay(n - 1);
  let result = "";
  let count = 1;
  for (let i = 1; i <= prev.length; i++) {
    if (prev[i] === prev[i - 1]) {
      count++;
    } else {
      result += count + prev[i - 1];
      count = 1;
    }
  }
  return result;
}
console.log(countAndSay(6));

hard

A. "13112221"

B. "312211"

C. "1113213211"

D. "21121314"

Solution

1. Step 1: List terms up to 6

   Term 1: "1"; Term 2: "11"; Term 3: "21"; Term 4: "1211"; Term 5: "111221"; Term 6: "312211".

2. Step 2: Confirm output matches term 6

   The function returns "312211" for n=6, matching "312211".

3. Final Answer:

   "312211" -> Option B

4. Quick Check:

   Term 6 = "312211" [OK]

Hint: Memorize first 6 terms or trace stepwise [OK]

Common Mistakes:

• Mixing up term 5 and 6
• Miscounting repeated digits
• Skipping recursive calls