Count ways to spell a number with repeated digits - GeeksforGeeks

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.

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;

}

Read full article from Count ways to spell a number with repeated digits - GeeksforGeeks