string - Subsequences whose sum of digits is divisible by 6 -

say have string characters nothing digits in [0 - 9] range. e.g: "2486". want find out subsequences sum of digits divisible 6. e.g: in "2486", subsequences - "6", "246" ( 2+ 4 + 6 = 12 divisible 6 ), "486" (4 + 8 + 6 = 18 divisible 6 ) etc. know generating 2^n combinations can this. that's costly. efficient way this?

edit:

i found following solution somewhere in quora.

int len,ar[maxlen],dp[maxlen][maxn];  int fun(int idx,int m)  {      if(idx==len)          return (m==0);      if(dp[idx][m]!=-1)          return dp[idx][m];      int ans=fun(idx+1,m);      ans+=fun(idx+1,(m*10+ar[idx])%n);      return dp[idx][m]=ans;  }  int main()  {      // input len , n , array      memset(dp,-1,sizeof(dp));      printf("%d\n",fun(0,0));                  return 0;  } 

can please explain logic behind code - 'm*10+ar[idx])%n' ? why m multiplied 10 here?

say have sequence of 16 digits generate 2¹⁶ subsequences , test them, 65536 operations.

or take first 8 digits , generate 2⁸ possible subsequences, , sort them based on result of sum modulo 6, , same last 8 digits. 512 operations.

then can generate subsequences of original 16 digit string divisible 6 taking each subsequence of first list modulo value equal 0 (including empty subsquence) , concatenating each subsequence of last list modulo value equal 0.

then take each subsequence of first list modulo value equal 1 , concatenate each subsequence of last list modulo value equal 5. 2 4, 3 3, 4 2 , 5 1.

so after initial cost of 512 operations can generate subsequences sum divisible 6. can apply algorithm recursively larger sequences.