Given a number num as a string and a number N. The task is to write a program which converts the given number num to another number after performing N steps. At each step, every digit of num will be written in the format [count][digit] in the new number, where count is the number of times a digit occurs consecutively in num.
Examples:
Input: num = “123”; n = 3
Output: 1321123113
For, n = 1: 123 becomes 1 time 1, 1 time 2, 1 time 3, hence number 111213
For, n = 2: 3 times 1, 1 time 2, 1 time 1, 1 time 3, hence number 31121113
For, n = 3: 1 time 3, 2 times 1, 1 time 2, 3 times 1, 1 time 3, hence number 1321123113Input: num = “1213”; n = 1
Output: 11121113
Approach:
Parse the string’s characters as a single digit and maintain a count for that digit till a different digit is found. Once a different digit is found, add the count of the digit to the new string and number to it. Once the string is parsed completely, recur for the function again with this new string till n steps are done.
Algorithm
- Define a function countDigits that takes two parameters: a string st and an integer n.
- If n is greater than 0, perform the following steps:
- a. Initialize cnt to 1 and create an empty string st2.
- b. Traverse the string st from index 1 to length-1.
- c. If the current character is equal to the previous character, increment cnt.
- d. If the current character is not equal to the previous character, append cnt and the previous character to st2, then reset cnt to 1.
- e. Append the count and last character to st2.
- f. Call the countDigits function recursively with st2 and n-1.
- If n is equal to 0, print the string st.
Below is the implementation of the above approach:
C++
// C++ program to convert number// to the format [count][digit] at every step#include <bits/stdc++.h>using namespace std;// Function to perform every stepvoid countDigits(string st, int n){ // perform N steps if (n > 0) { int cnt = 1, i; string st2 = ""; // Traverse in the string for (i = 1; i < st.length(); i++) { if (st[i] == st[i - 1]) cnt++; else { st2 += ('0' + cnt); st2 += st[i - 1]; cnt = 1; } } // for last digit st2 += ('0' + cnt); st2 += st[i - 1]; // recur for current string countDigits(st2, --n); } else cout << st;}// Driver Codeint main(){ string num = "123"; int n = 3; countDigits(num, n); return 0;} |
Java
// Java program to convert number // to the format [count][digit] at every stepclass GFG { // Function to perform every step public static void countDigits(String st, int n) { // perform N steps if (n > 0) { int cnt = 1, i; String st2 = ""; // Traverse in the string for (i = 1; i < st.length(); i++) { if (st.charAt(i) == st.charAt(i - 1)) cnt++; else { st2 += ((char) 0 + (char) cnt); st2 += st.charAt(i - 1); cnt = 1; } } // for last digit st2 += ((char) 0 + (char) cnt); st2 += st.charAt(i - 1); // recur for current string countDigits(st2, --n); } else System.out.print(st); } // Driver Code public static void main(String[] args) { String num = "123"; int n = 3; countDigits(num, n); }}// This code is contributed by// sanjeev2552 |
Python3
# Python program to convert number# to the format [count][digit] at every step# Function to perform every stepdef countDigits(st, n): # perform N steps if (n > 0) : cnt = 1 i = 0 st2 = "" i = 1 # Traverse in the string while (i < len(st) ) : if (st[i] == st[i - 1]): cnt = cnt + 1 else : st2 += chr(48 + cnt) st2 += st[i - 1] cnt = 1 i = i + 1 # for last digit st2 += chr(48 + cnt) st2 += st[i - 1] # recur for current string countDigits(st2, n - 1) n = n - 1; else: print(st)# Driver Codenum = "123"n = 3countDigits(num, n)# This code is contributed by Arnab Kundu |
C#
// C# program to convert number // to the format [count][digit] at every stepusing System;class GFG {// Function to perform every steppublic static void countDigits(string st, int n){ // perform N steps if (n > 0) { int cnt = 1, i; string st2 = ""; // Traverse in the string for (i = 1; i < st.Length; i++) { if (st[(i)] == st[(i - 1)]) cnt++; else { st2 += ((char) 0 + (char) cnt); st2 += st[(i - 1)]; cnt = 1; } } // for last digit st2 += ((char) 0 + (char) cnt); st2 += st[(i - 1)]; // recur for current string countDigits(st2, --n); } else Console.Write(st);}// Driver Codepublic static void Main() { string num = "123"; int n = 3; countDigits(num, n);}}// This code is contributed by// Code_Mech. |
Javascript
<script>// Javascript program to convert number // to the format [count][digit] at every step// Function to perform every stepfunction countDigits(st, n){ // Perform N steps if (n > 0) { let cnt = 1, i; let st2 = ""; // Traverse in the string for(i = 1; i < st.length; i++) { if (st[i] == st[i - 1]) cnt++; else { st2 += String.fromCharCode( '0'.charCodeAt() + cnt); st2 += st[i - 1]; cnt = 1; } } // For last digit st2 += String.fromCharCode( '0'.charCodeAt() + cnt); st2 += st[i - 1]; // Recur for current string countDigits(st2, --n); } else document.write(st);}// Driver codelet num = "123";let n = 3;countDigits(num, n);// This code is contributed by decode2207</script> |
Output
1321123113
Method 2 (iterative approach)
The idea is to use iterative approach, where a loop is used to repeat the process N times. In each iteration, the program constructs a new string by counting consecutive digits in the previous string, and updates the previous string to be the new string.
Algorithm
- 1. Define a function countAndSay that takes a string num and an integer n as inputs, and returns a string.
- 2. Loop for n iterations:
- a. Initialize an empty string newNum and variables count and prev to 1 and the first digit of num, respectively.
- b. Loop through the digits of num from the second digit to the last:
- i. If the current digit is the same as prev, increment count by 1.
- ii. If the current digit is different from prev, append count and prev to newNum, reset count to 1, and update prev to the current digit.
- c. Append count and prev to newNum to include the last consecutive sequence of digits.
- d. Update num to be equal to newNum for the next iteration.
- 3. Return num as the final output after n iterations.
C++
#include <iostream>#include <string>using namespace std;string countAndSay(string num, int n) { // Loop for n iterations for (int i = 0; i < n; i++) { // Initialize variables for the new number string newNum = ""; int count = 1; char prev = num[0]; // Loop through the digits of the current number for (int j = 1; j < num.length(); j++) { // If the current digit is the same as the previous digit, // increase the count of consecutive digits if (num[j] == prev) { count++; } else { // Otherwise, append the count and the previous digit // to the new number, and reset the count and the previous digit newNum += to_string(count) + prev; count = 1; prev = num[j]; } } // Append the count and the previous digit of the last // consecutive sequence to the new number newNum += to_string(count) + prev; // Update the current number to be the new number num = newNum; } // Return the final number after n iterations return num;}int main() { // Sample input values string num = "123"; int n = 3; // Call the countAndSay function with the sample input values string result = countAndSay(num, n); // Print the result to the console cout << result << endl; return 0;} |
Java
import java.util.*;public class GFG { public static String countAndSay(String num, int n) { // Loop for n iterations for (int i = 0; i < n; i++) { // Initialize variables for the new number StringBuilder newNum = new StringBuilder(); int count = 1; char prev = num.charAt(0); // Loop through the digits of the current number for (int j = 1; j < num.length(); j++) { // If the current digit is the same as the // previous digit, increase the count of // consecutive digits if (num.charAt(j) == prev) { count++; } else { // Otherwise, append the count and the // previous digit to the new number, and // reset the count and the previous // digit newNum.append(count).append(prev); count = 1; prev = num.charAt(j); } } // Append the count and the previous digit of // the last consecutive sequence to the new // number newNum.append(count).append(prev); // Update the current number to be the new // number num = newNum.toString(); } // Return the final number after n iterations return num; } public static void main(String[] args) { // Sample input values String num = "123"; int n = 3; // Call the countAndSay function with the sample // input values String result = countAndSay(num, n); System.out.println(result); }}// This code is contributed by akshitaguprzj3 |
Python3
def count_and_say(num, n): # Loop for n iterations for _ in range(n): # Initialize variables for the new number new_num = "" count = 1 prev = num[0] # Loop through the digits of the current number for j in range(1, len(num)): # If the current digit is the same as the previous digit, # increase the count of consecutive digits if num[j] == prev: count += 1 else: # Otherwise, append the count and the previous digit # to the new number, and reset the count and the previous digit new_num += str(count) + prev count = 1 prev = num[j] # Append the count and the previous digit of the last # consecutive sequence to the new number new_num += str(count) + prev # Update the current number to be the new number num = new_num # Return the final number after n iterations return num# Sample input valuesnum = "123"n = 3# Call the count_and_say function with the sample input valuesresult = count_and_say(num, n)# Print the result to the consoleprint(result) |
C#
using System;public class Program{ public static string CountAndSay(string num, int n) { // Loop for n iterations for (int i = 0; i < n; i++) { // Initialize variables for the new number string newNum = ""; int count = 1; char prev = num[0]; // Loop through the digits of the current number for (int j = 1; j < num.Length; j++) { // If the current digit is the same as the previous digit, // increase the count of consecutive digits if (num[j] == prev) { count++; } else { // Otherwise, append the count and the previous digit // to the new number, and reset the count and the previous digit newNum += count.ToString() + prev; count = 1; prev = num[j]; } } // Append the count and the previous digit of the last // consecutive sequence to the new number newNum += count.ToString() + prev; // Update the current number to be the new number num = newNum; } // Return the final number after n iterations return num; } public static void Main(string[] args) { // Sample input values string num = "123"; int n = 3; // Call the CountAndSay function with the sample input values string result = CountAndSay(num, n); // Print the result to the console Console.WriteLine(result); }}// This code is contributed by akshitaguprzj3 |
Javascript
// Function to generate the count-and-say sequence for a given number and iterationsfunction countAndSay(num, n) { // Loop for n iterations for (let i = 0; i < n; i++) { // Initialize variables for the new number let newNum = ""; let count = 1; let prev = num[0]; // Loop through the digits of the current number for (let j = 1; j < num.length; j++) { // If the current digit is the same as the previous digit, // increase the count of consecutive digits if (num[j] === prev) { count++; } else { // Otherwise, append the count and the previous digit // to the new number, and reset the count and the previous digit newNum += count + prev; count = 1; prev = num[j]; } } // Append the count and the previous digit of the last // consecutive sequence to the new number newNum += count + prev; // Update the current number to be the new number num = newNum; } // Return the final number after n iterations return num;}// Sample input valueslet num = "123";let n = 3;// Call the countAndSay function with the sample input valueslet result = countAndSay(num, n);// Print the result to the consoleconsole.log(result);// This Code is Contributed by Shivam Tiwari |
Output
1321123113
Time complexity: O(n * m), where n is the number of iterations and m is the length of the string representing the current term in the sequence
Space complexity: O(n * m), as it stores a new string of length m for each iteration of the loop.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
