Count ways to spell a number with repeated digits - GeeksforGeeks
Given a string that contains digits of a number. The number may contain many same continuous digits in it. The task is to count number of ways to spell the number.
For example, consider 8884441100, one can spell it simply as triple nine triple four double two and double zero. One can also spell as double nine, nine, four, double four, two, two, double zero.
Read full article from Count ways to spell a number with repeated digits - GeeksforGeeks
Given a string that contains digits of a number. The number may contain many same continuous digits in it. The task is to count number of ways to spell the number.
For example, consider 8884441100, one can spell it simply as triple nine triple four double two and double zero. One can also spell as double nine, nine, four, double four, two, two, double zero.
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
This is a simple problem of permutation and combination. If we take example test case given in the question, 11112. The answer depends on the number of possible combinations of 1111. The number of combinations of “1111” is 2^3 = 8. As our combinations will depend on whether we choose a particular 1 and for “2” there will be only one possibility 2^0 = 1, so answer for “11112” will be 8*1 = 8.
So, the approach is to count the particular continuous digit in string and multiply 2^(count-1) with previous result.
So, the approach is to count the particular continuous digit in string and multiply 2^(count-1) with previous result.
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;
}