efficiente algoritmo per contare il numero di sottosequenze divisibile per 6

Question

Data una stringa di cifre decimali, devo trovare il numero di tutte le sottosequenze divisibili per 6.

1 ≤ value of String ≤ 10^6 

Ho provato l'approccio ingenuo di iterare su tutte le possibili sottosequenze e ottenere la risposta, ma ciò non è abbastanza veloce, specialmente con un limite superiore così grande sulla lunghezza della stringa. Quindi ho provato un approccio DP ma non sono riuscito a codificare la soluzione DP per un determinato intervallo. Qualcuno può fornire qualche vantaggio in questo problema?

Sample Input 
1232 
Output 
3 
Strings Possible - 12,12,132 
//Ans should be modulo 10^9 + 7 

Di seguito si riporta il codice DP (non del tutto sicuro su di esso) per trovare il numero totale di sottosequenze divisibile per 3.Now per verificare la presenza di 6, abbiamo anche bisogno di incorporare la divisibilità per 2 che sta creando problemi per me.

for(i=0 ; i<n ; i++) { 
    for(j=0 ; j<3 ; j++) { 
     dp[i][j]=0 ; 
    } 
    int dig = (str[i]-'0')%3 ; 
    dp[i][dig]++ ; 
    if(i>0) { 
     for(j=0 ; j<3 ; j++) { 
      if(dig % 3 == 0) { 
       dp[i][j] += dp[i-1][j]; 
      } 
      if(dig % 3 == 1) { 
       dp[i][j] += dp[i-1][(j+2)%3]; 
      } 
      if(dig % 3 == 2) { 
       dp[i][j] += dp[i-1][(j+1)%3]; 
      } 
     } 
    } 
} 
long long ans = 0; 
for(i=0 ; i<n ; i++) { 
    ans += dp[i][0] ; 
} 
return ans; 

Answer 1

Questo problema può essere risolto in tempo lineare, O (N) e spazio lineare O (N), N essendo lunghezza della stringa se ci sono due consideriamo solo sottostringhe. Sto cercando di creare un algoritmo per le sottosequenze.

Punti chiave:

. Tutte le sottostringhe che sono divisibili per 6 sono divisibili per 2 e 3 e ci concentreremo sulla divisibilità di questi due numeri.

. Ciò significa che tutte le sottostringhe candidate devono terminare con 0 o 2 o 4 o 6 o 8, per soddisfare la divisibilità per 2 E

. Somma delle cifre della stringa deve essere divisibile per 3.

Ora prima prendiamo un array arr, di lunghezza N. Si riempie è tale che

arr[i] = 1 , if ith digit in substring is 0 or 2 or 4 or 6 or 8. 

else arr[i] = 0. 

Questo può essere facilmente effettuata in un'unica attraversamento della stringa.

Quello che otteniamo è ora sappiamo che tutti sono sottostringhe candidati terminerà alle indice i di corda in modo tale che arr[i] = 1, perché dobbiamo soddisfare divisibilità per 2.

Ora prendete un altro array arr1, inizializzato a 0 per tutto indexes.We riempirlo tale che

arr1[i] = 1, only if sum of digits from index 0 to index i is divisible by 3 

or from index j to i is divisible by 3, such that j < i. 

else arr1[i] = 0 

Per riempimento della matrice arr1, algoritmo è il seguente:

sum = 0 
for(i = 0 to length of string - 1) 
{ 
sum = sum + digit at index i; 
if(sum%3 == 0) 
{ 
    arr1[i] = 1 
    sum = 0 
} 
} 

Ora dobbiamo occuparci del fatto anche se la somma delle cifre da 0 all'indice i è divisibile per 3, è possibile che la somma di cifre sia anche divisibile per 3 dall'indice j a i, tale che 0 < j < i.

Per questo abbiamo bisogno di un altro array, che tenga traccia di quante sottostringhe abbiamo trovato fino ad ora.

Lasciate che la matrice sia track, in modo tale che

track[i] = x, if there are x number of 1's in array arr1 for indices j < i. 

Noi non abbiamo bisogno di un altro attraversamento possiamo modificare il nostro algoritmo precedente come:

initialize array track to be 0 for all entries. 
sum = 0 
found = -1 
for(i = 0 to length of string - 1) 
{ 
sum = sum + digit at index i; 
if(sum%3 == 0) 
    { 
    arr1[i] = 1 
    ++found 
    track[i] = found 
    sum = 0 
} 

Ora viene la parte importante, che sta contando,

rivendicazione:

012.351.641.061.

Una stringa termina al indice i contribuirà solo a contare se e solo se:

arr[i] == 1 and arr1[i] == 1 

E 'chiaro perché dobbiamo soddisfare divisibilità sia da 2 e 3. E il contributo alla conteggio sarebbe:

count = count + track[i] + 1 

1 è aggiunto a causa della j < i in

track[i] = x, if there are x number of 1's in array arr1 for indices j < i. 

L'algoritmo è abbastanza facile da implementare, prendere che come un esercizio.

Answer 2

Soluzione ricorsiva esponenziale (per casi generici) che si traduce in lineare se il valore massimo che corrisponde può rappresentare 1e6.

def recurse(x, substr, input): 
    if x%6 == 0: 
    print(x) 
    if len(substr) == 6: // as the value represented by string may not be > 1e6 
    return 
    if input: 
    recurse(x+input[0], substr + input[0], input[1:]) // grow the "window" 
    recurse(x, substr, input[1:]) // shift the "window" 

input = "123163736395067251284059573634848487474" 

recurse(input) 

Answer 3

Sia SS(x, k, m) = il numero di sottosequenze della stringa x rappresenta un numero che è uguale a k modulo m.

SS([], k, m) = 1 if k == 0 otherwise 0 -- (see footnote at end) 
SS(x + [d], k, m) = SS(x, k, m) + sum(SS(x, j, m) where j*10+d == k modulo m) 

Cioè, se si aggiunge una cifra di x, allora le sottosequenze tale somma a k sono sottosequenze di x tale somma a K, oltre a sottosequenze di x tale somma a j dove (10 * j) più il la nuova cifra è k modulo m.

Che si trasforma in un bel programma dinamico, che se N è la lunghezza della stringa e m il numero per cui le sottosequenze devono essere divisibili per, viene eseguito in O (Nm + m^2) ora e utilizza O (m) spazio. Per m = 6, questo è O (N) tempo e O (1) spazio.

# count subsequences with a sum divisible by m. 
def subseq(N, m): 
    a = [1] + [0] * (m - 1) 
    indexes = [[j for j in xrange(m) if (10*j-i)%m == 0] for i in xrange(m)] 
    for digit in N: 
     a = [a[i] + sum(a[j] for j in indexes[(i - digit) % m]) for i in xrange(m)] 
    return a[0] - 1 

print subseq(map(int, '1232'), 6) 

nota: la definizione di SS conta la lista vuota come 0, ma la stringa vuota non è un numero valido, quindi la funzione sottrae prima di tornare.