반복되는 숫자로 숫자의 철자를 계산하는 방법

GfG Practice에서 사용해 보세요. ' title=

#practiceLinkDiv { 표시: 없음 !중요; }

숫자의 자릿수가 포함된 문자열이 제공됩니다. 숫자에는 동일한 연속 숫자가 많이 포함될 수 있습니다. 이 작업은 숫자를 철자하는 방법의 수를 세는 것입니다.
예를 들어 8884441100을 생각해 보면 간단히 트리플 8 트리플 4 더블 2 및 더블 0으로 철자할 수 있습니다. 더블 8 8 4 더블 4 2 2 더블 0으로 철자를 쓸 수도 있습니다.

예:

Input : num = 100 Output : 2 The number 100 has only 2 possibilities 1) one zero zero 2) one double zero. Input : num = 11112 Output: 8 1 1 1 1 2 11 1 1 2 1 1 11 2 1 11 1 2 11 11 2 1 111 2 111 1 2 1111 2 Input : num = 8884441100 Output: 64 Input : num = 12345 Output: 1 Input : num = 11111 Output: 16

Recommended Practice 숫자 철자를 입력하세요 시도해 보세요!

순열과 조합의 간단한 문제입니다. 질문 11112에 제공된 테스트 사례를 예로 들면, 대답은 1111의 가능한 하위 문자열 수에 따라 달라집니다. '1111'의 가능한 하위 문자열 수는 4 - 1 = 3개의 구분 기호 '|'의 조합 수이므로 2^3 = 8입니다. 문자열의 두 문자(문자열로 표시되는 숫자의 자릿수) 사이: '1|1|1|1'. 조합은 특정 1을 선택하는지 여부에 따라 달라지며 '2'의 경우 가능성은 2^0 = 1 하나만 있으므로 '11112'에 대한 답은 8*1 = 8이 됩니다.

따라서 접근 방식은 문자열의 특정 연속 숫자를 계산하고 이전 결과에 2^(count-1)을 곱하는 것입니다.

C++

// C++ program to count number of ways we // can spell a number #include   using namespace std; typedef long long int ll; // Function to calculate all possible spells of // a number with repeated digits // num --> string which is favourite number ll spellsCount(string num) {  int n = num.length();  // final count of total possible spells  ll result = 1;  // iterate through complete number  for (int i=0; i<n; i++)  {  // count contiguous frequency of particular  // digit num[i]  int count = 1;  while (i < n-1 && num[i+1] == num[i])  {  count++;  i++;  }  // Compute 2^(count-1) and multiply with result   result = result * pow(2 count-1);  }  return result; } // Driver program to run the case int main() {  string num = '11112';  cout << spellsCount(num);  return 0; }

Java

// Java program to count number of ways we // can spell a number import java.io.*; class GFG {    // Function to calculate all possible   // spells of a number with repeated digits  // num --> string which is favourite number  static long spellsCount(String num)  {    int n = num.length();  // final count of total possible spells  long result = 1;  // iterate through complete number  for (int i = 0; i < n; i++) {    // count contiguous frequency of   // particular digit num[i]  int count = 1;    while (i < n - 1 && num.charAt(i + 1)   == num.charAt(i)) {    count++;  i++;  }  // Compute 2^(count-1) and multiply   // with result  result = result *   (long)Math.pow(2 count - 1);  }  return result;  }  public static void main(String[] args)  {  String num = '11112';  System.out.print(spellsCount(num));  } } // This code is contributed by Anant Agarwal.

Python3

# Python3 program to count number of # ways we can spell a number # Function to calculate all possible  # spells of a number with repeated  # digits num --> string which is  # favourite number def spellsCount(num): n = len(num); # final count of total # possible spells result = 1; # iterate through complete # number i = 0; while(i<n): # count contiguous frequency  # of particular digit num[i] count = 1; while (i < n - 1 and num[i + 1] == num[i]): count += 1; i += 1; # Compute 2^(count-1) and # multiply with result  result = result * int(pow(2 count - 1)); i += 1; return result; # Driver Code num = '11112'; print(spellsCount(num)); # This code is contributed # by mits

// C# program to count number of ways we // can spell a number using System; class GFG {    // Function to calculate all possible   // spells of a number with repeated   // digits num --> string which is  // favourite number  static long spellsCount(String num)  {    int n = num.Length;  // final count of total possible  // spells  long result = 1;  // iterate through complete number  for (int i = 0; i < n; i++)  {    // count contiguous frequency of   // particular digit num[i]  int count = 1;    while (i < n - 1 && num[i + 1]   == num[i])  {  count++;  i++;  }  // Compute 2^(count-1) and multiply   // with result  result = result *   (long)Math.Pow(2 count - 1);  }    return result;  }  // Driver code  public static void Main()  {  String num = '11112';  Console.Write(spellsCount(num));  } } // This code is contributed by nitin mittal.

PHP

 // PHP program to count  // number of ways we // can spell a number // Function to calculate  // all possible spells of // a number with repeated  // digits num --> string // which is favourite number function spellsCount($num) { $n = strlen($num); // final count of total // possible spells $result = 1; // iterate through  // complete number for ($i = 0; $i < $n; $i++) { // count contiguous frequency  // of particular digit num[i] $count = 1; while ($i < $n - 1 && $num[$i + 1] == $num[$i]) { $count++; $i++; } // Compute 2^(count-1) and // multiply with result  $result = $result * pow(2 $count - 1); } return $result; } // Driver Code $num = '11112'; echo spellsCount($num); // This code is contributed // by nitin mittal.  ?>

JavaScript

<script> // Javascript program to count number of  // ways we can spell a number // Function to calculate all possible  // spells of a number with repeated  // digits num --> string which is // favourite number function spellsCount(num) {  let n = num.length;  // Final count of total possible  // spells  let result = 1;  // Iterate through complete number  for (let i = 0; i < n; i++)  {    // Count contiguous frequency of   // particular digit num[i]  let count = 1;    while (i < n - 1 &&   num[i + 1] == num[i])  {  count++;  i++;  }  // Compute 2^(count-1) and multiply   // with result  result = result *   Math.pow(2 count - 1);  }  return result; }   // Driver code let num = '11112'; document.write(spellsCount(num)); // This code is contributed by code_hunt   </script>

산출

시간 복잡도: O(n*log(n))
보조 공간: 오(1)

이 문제를 해결하기 위한 다른 접근 방식이 있다면 공유해 주세요.