Find a subsequence of a string whose length is 10,000

Question

I have a string whose size can be the same as "10000". I have to count these SEQUENCES, which are divided by 9.

SUBSEQUENCE: A subsequence is a location in which the character order of a given string is maintained. For ex: if the given string is 10292, then some of its subsequences are 1, 102, 10, 19, 12, 12 (12 twice twice), 129, 029, 09, 092, etc. Some numbers that are not subsequences of this line: 201 (2 and 0 cannot be up to 1), 921, 0291, etc.

I tried to generate all the powersets of the given string using a bit shift and check each string if it is divisible by 9. But this works fine as long as the string length is <= 10. After that I don't get the correct subsequences (in 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 avoid this problem with the recursive O(n) algorithm.

The idea is this: at each step, separate two subsequences and determine (recursively) how many sequences have the sum of their digits i % 9 , where i is in the range from 0 to 8 , then you create the same table for the entire range by "merging" "of two tables in O(1) as follows. Let's say L is a table for the left split and R for the right, and you need to build table F for the entire 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 main case for a subsequence of only one digit d is obvious: just set F[d % 9] = 1 and all other entries are zero.

Full implementation of C ++ 11:

 #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; } 

Answer 2

I had an idea!

Since you only need to count substrings, you don't care what they really are. So instead, you can just save the number of possible amounts.

Then, what if you had a function that could combine the counter tables of two tweaks and give you counts of their combinations?

And since I know this was a terrible explanation, I will give an example. Say that you are assigned a number:

 2493 

Divide it in half and continue the division until you get individual numbers:

  2493 / \ 24 93 /\ /\ 2 4 9 3 

What can 2 summarize? Easy: 2 . And 4 can only stack up to 4 . You can build tables of how many substrings are added to each value (mod 9):

  0 1 2 3 4 5 6 7 8 2: 0 0 1 0 0 0 0 0 0 4: 0 0 0 0 1 0 0 0 0 9: 1 0 0 0 0 0 0 0 0 3: 0 0 0 1 0 0 0 0 0 

Simple joining of two tables. Add the first table, the second table and each combination of the two modes 9 (for the first combination this is equivalent to 2 , 4 and 24 ; for the second, 9 , 3 and 93 ):

  0 1 2 3 4 5 6 7 8 24: 0 0 1 0 1 0 1 0 0 93: 1 0 0 2 0 0 0 0 0 

Then do it again:

  0 1 2 3 4 5 6 7 8 2493: 3 0 2 2 2 2 2 2 0 

And here is your answer, sitting in column 0 : 3 . This corresponds to substrings 243 , 2493 and 9 . You do not know this, though, because you just saved the score - and, fortunately, you don't care!

After implementation, this will give you O(n) performance - you just need to figure out how to join tables in O(1) . But hey is homework, isn't it? Good luck

Answer 3

If you use int , you should not shift it too much. If you do this, you will set the sign bit. Use unsigned int . Or don't push too much. You can change the edit after completion if you insist on int .

for

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

printf may have problems displaying long-int types. Have you tried cout?

Answer 4

Here's the C ++ code according to the Akappa algorithm. However, this algorithm fails for numbers that contain one or more 0s, i.e. In cases of "10292" and "0189", but give the correct answers for "1292" and "189". I would be grateful if anyone could debug this to give answers to all cases.

 #include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<string> #include<cstring> #include<vector> #include<stack> #include<sstream> #include<algorithm> #include<cctype> #include<list> #include<set> #include<set> #include<map> using namespace std; typedef vector<int> table; table count(string::iterator beg, string::iterator end) { table F(9); 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() { cout << count("1234")[0] << endl; cout << count("12349")[0] << endl; cout << count("9999")[0] << endl; cout << count("1292")[0] << endl;cout << count("189")[0] << endl; cout << count("10292")[0] << endl;cout << count("0189")[0] << endl; system("pause"); }