Find subsequences of a string whose length is as large as 10,000

Question

I have a string whose size can be as large as "10,000". I have to count those SUBSEQUENCES which are divisible by 9.

SUBSEQUENCE: A subsequence is an arrangement in which the order of characters of given string is maintained. For ex: if given string is 10292 then some of its subsequences are 1, 102, 10, 19, 12, 12(12 is twice as 2 comes twice), 129, 029, 09, 092, etc. Some numbers which are not subsequences of given string are: 201(2 and 0 can't come before 1), 921, 0291, etc.

I have tried to generate all subsequences(powerset) of given string using bit shifting and checking each string if it is divisible by 9. But this works fine as long as length of string is <=10. After that, I don't get proper subsequences(some subsequences are displayed negative numbers).

Below is my code:

    scanf("%s", &str); //input string 

    int n=strlen(str); //find length of string

    //loop to generate subsequences
    for(i=1;i<(1<<n);++i){

        string subseq;

        for(j=0;j<n;++j){

            if(i&(1<<j)){

                subseq+=str[j]; // generate subsequence
            }
        }

        //convert generated subseq to int; number is 'long' tpye
        number=atol(subseq.c_str());printf("%ld\n", number); 

        //ignore 0 and check if number divisible by 9
        if(number!=0&&number%9==0)count++;
    }

        printf("%ld\n", count);

Answer 1

Since a number is divisible by nine if and only if the sum of its digits is divisible by nine, you can get away with this problem with a O(n) recursive algorithm.

The idea is the following: at each step, split in two the subsequence and determine (recursively) how many sequences have the sum of its digits be i % 9, where i ranges from 0 to 8. Then, you build up this very same table for the whole range by "merging" the two tables in O(1) in the following way. Let's say L is the table for the left split and R for the right one and you need to build the table F for the whole range.

Then you have:

for (i = 0; i < 9; i++) {
  F[i] = L[i] + R[i];
  for (j = 0; j < 9; j++) {
    if (j <= i)
      F[i] += L[j] * R[i - j]
    else
      F[i] += L[j] * R[9 + i - j]
  }
}

The base case for a subsequence of only one digit d is obvious: just set F[d % 9] = 1 and all the other entries to zero.

A full C++11 implementation:

#include <iostream>
#include <array>
#include <tuple>
#include <string>

typedef std::array<unsigned int, 9> table;

using std::tuple;
using std::string;

table count(string::iterator beg, string::iterator end)
{
    table F;
    std::fill(F.begin(), F.end(), 0);
    if (beg == end)
        return F;
    if (beg + 1 == end) {
        F[(*beg - '0') % 9] = 1;
        return F;
    }
    size_t distance = std::distance(beg, end);
    string::iterator mid = beg + (distance / 2);
    table L = count(beg, mid);
    table R = count(mid, end);

    for (unsigned int i = 0; i < 9; i++) {
        F[i] = L[i] + R[i];
        for(unsigned int j = 0; j < 9; j++) {
            if (j <= i)
                F[i] += L[j] * R[i - j];
            else
                F[i] += L[j] * R[9 + i - j];
        }
    }
    return F;
}

table count(std::string s)
{
    return count(s.begin(), s.end());
}

int main(void)
{
    using std::cout;
    using std::endl;
    cout << count("1234")[0] << endl;
    cout << count("12349")[0] << endl;
    cout << count("9999")[0] << endl;
}