#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)
Ако имате друг подход за решаване на този проблем, моля, споделете.