数字が繰り返される数字の綴り方を数えます
GfG Practice で試してみる 
#practiceLinkDiv { 表示: なし !重要; }
出力
#practiceLinkDiv { 表示: なし !重要; } 数値の桁を含む文字列が与えられます。番号には、同じ連続数字が多数含まれる場合があります。課題は、数字の綴り方の数を数えるということです。
たとえば、8884441100 を考えてみると、単にトリプル 8、トリプル 4、ダブル 2、ダブル ゼロと綴ることができます。 double 8 8 4 double 4 2 2 double 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: 16Recommended Practice 数字を綴ってください 試してみてください!
これは順列と組み合わせの単純な問題です。質問 11112 で示されたテスト ケースの例を考えてみます。答えは 1111 の可能な部分文字列の数によって異なります。「1111」の可能な部分文字列の数は 2^3 = 8 です。これは、4 - 1 = 3 個の区切り文字 '|' の組み合わせの数であるためです。文字列の 2 つの文字の間 (文字列で表される数値の桁): '1|1|1|1'。組み合わせは特定の 1 を選択するかどうかに依存し、「2」の場合は 2^0 = 1 の可能性が 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# // 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>
出力
8
時間計算量: O(n*log(n))
補助スペース: ○(1)
この問題を解決する別のアプローチがある場合は、共有してください。
