#practiceLinkDiv { display: none !important; }Дано рядок, який містить цифри числа. Число може містити багато однакових послідовних цифр. Завдання полягає в тому, щоб підрахувати кількість способів написання числа.
Наприклад, розглянемо 8884441100, його можна написати просто як потрійний вісім потрійний чотири подвійний два і подвійний нуль. Можна також писати як подвійні вісім вісім чотири подвійні чотири два два подвійні нуль.
Приклади:
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 роздільників '|' між двома символами рядка (цифрами числа, представленого рядком): '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
// 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 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 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. ?> <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)
Якщо у вас є інший підхід до вирішення цієї проблеми, поділіться.