Algoritmo efficiente per contare il numero di sottostringhe divisibile per 3

Simpatico problema di programmazione dinamica. Ecco una soluzione Java e una rapida spiegazione.

La domanda di base da porsi è se conoscessi il sottoproblema X, potrei risolvere facilmente il problema con Y.

In questo caso, il problema Y è il numero di sottostringhe divisibile per 3, il sottoproblema X è il numero di sottostringhe modulo 3 che termina con il carattere precedente per ogni possibile mod (che è rimasto 0, 1 e 2).

Se sai che nella posizione precedente, c'erano due sottostringhe che terminavano lì che avevano un residuo di zero, 3 con un residuo di uno, e 1 con un residuo di due, quindi dato il numero corrente e il suo residuo, è banale determinare i residui di tutte le stringhe che terminano con il carattere corrente.

Se il residuo del numero corrente è uno (ad esempio, il numero è 1, 4 o 7), le sottostringhe che terminano sul numero precedente con un residuo di uno ora hanno un residuo di due, quelle con un residuo di due ora hanno un residuo di zero e quelli con un residuo di zero ora hanno un residuo di uno più 1 in più per la cifra corrente da quando hai aggiunto una nuova sottostringa possibile di lunghezza uno.

Ad esempio, se si avesse la stringa 521438 e si conoscesse il numero di stringhe che terminavano al 3 per ciascun residuo (2, 2 e 1 rispettivamente per i residui 0, 1 e 2), e poiché 8 mod 3 è 2, sai che tutti quelli con residuo zero ora hanno il residuo 2, quelli con il residuo due ora ne hanno il residuo uno e quelli con il residuo uno ora hanno il residuo zero, quindi (2, 1 e 2 in modo ripetitivo), in più hai un nuovo stringa di residuo 2 in modo da avere 2, 1 e 3 ora incluso il numero corrente.

Dopo averlo elaborato in tempo lineare, per tutte le sottostringhe, si sommano tutti quelli con residui zero che terminano in tutte le posizioni.

Ecco il codice:

// Takes constant space and linear time.
public static void main(String[] args) {

    // You really only need these numbers mod 3.
    int[] s = new int [] { 5,8,1,4,6,2 };
    int left = 3;
    int right = 4;

    int[] found = new int[3];
    int[] last_found = new int[3];
    int sum_found = 0;

    for(int i = left; i <= right; ++i) {

        int res = s[i-1] % 3;

        // leaving the +0 just to show the symmetry.
        // Basically, rotate by the residue and +1 for the new substring.
        // This can be done as a single array, but this is clearer I think.
        // (Also, a proper mathematical modulus would be easier too.)
        found[(res+0) % 3] = last_found[0] + 1;
        found[(res+1) % 3] = last_found[1];
        found[(res+2) % 3] = last_found[2];

        sum_found += found[0];

        // Swap the current and last arrays to make top of the loop simpler.
        int[] swap = last_found;
        last_found = found; 
        found = swap;
    }

    System.out.println( sum_found );
}

Modifica codice

Il codice sopra ha rimosso la tabella e tiene semplicemente traccia dell'ultima posizione. Lo fa con due array di lunghezza tre e si scambia tra loro. Potrebbe essere fatto con un singolo array, ma rende il codice più complesso (e probabilmente non ha nemmeno un rendimento migliore nel senso di micro-ottimizzazione).

Ora è tempo lineare e spazio costante mentre obbedisci alle richieste Left e Right. È come una serie di altri algoritmi DP, se si nota ogni iterazione si sta solo guardando indietro le iterazioni Ith-1, quindi di solito si può escludere l'intera tabella.

Inoltre tiene traccia della somma insieme al modo (ora richiesto poiché l'array finale non esiste più neanche). Inizialmente non ho compreso completamente il problema e sembra che abbia subito alcune modifiche lungo il percorso.

Ecco una soluzione Python al problema. È fondamentalmente la stessa di @JasonN. Implementa anche una funzione che restituisce il valore per diverse coppie di L e R. Utilizza meno memoria quando esegue i calcoli preliminari. Puoi eseguirlo qui

#http://programmers.stackexchange.com/q/268022/51441


# s:
#   input digit string that should be checked
# L:
#   the start of the substring that should be investigated
# L:
#   the end of the substring that should be investigated
# cnt:
#   number of 3divisble substrings found so far
# ss0:
#   number of substrings that end at the current position
#   and are divisible by 3
# ss1:
#   number of substrings that end at the current position
#   and have the remainder 1 when divided by 3
# ss2:
#   number of substrings that end at the current position
#   and have the remainder 2 when divided by 3


def ss(s,L,R):
    cnt=0
    (ss0,ss1,ss2)=(0,0,0)
    for i in range(L,R+1):
        r=int(s[i])%3
        if r==0:
            ss0+=1
        elif r==1:
            (ss0,ss1,ss2)=(ss2,ss0,ss1)
            ss1+=1
        elif r==2:
            (ss0,ss1,ss2)=(ss1,ss2,ss0)
            ss2+=1
        cnt+=ss0
    return(cnt)

print(ss('392301',0,len('392301')-1))
print(ss('2035498',2,5))

Sappiamo che Un numero è divisibile per 3 se la somma delle sue cifre è divisibile per 3 (secondo le regole di divisibilità di 3). Vi è O(n^2) soluzione di programmazione dinamica (pre-elaborazione) e O(1) di tempo costante per ogni query.

Lascia che arr[i] sia array contenente elementi dati ( 1....N ) e query[i][j] denota # di sottostringhe divisibili per 3 da [i, j]

for(int i = 1; i <= N; i++) {
    query[i][i] = (arr[i] % 3 == 0); // i.e. # of substrings divisible by 3 in [4, 4] is 1 if arr[4] is divisble by 3 otherwise 0
    arr[i] += arr[i - 1]; // arr[i] will contain cumulative sum of 1...i
}

// 
for(int i = N - 1; i > 0; i--) {
    for(int j = i + 1; j <= N; j++) {
        // exclusion-inclusion principle. # of substrings in [1, 7] will be - 
        // #1 sum of # of substrings in [1, 6] and [2, 7]. 
        //    As [2, 6] is included two times, so we need to subtract it one time
        // #2 plus 1 if substring [1, 7] is divisble by 3, 0 otherwise

        // #1
        query[i][j] = query[i][j - 1] + query[i + 1][j] - query[i + 1][j - 1];
        // #2
        // arr[j] contains sum of 1...j. 
        // so arr[j] - arr[i - 1] contains sum of [i...j]
        // number constructed from substring [i...j] is divisble by 3 
        // iff summation of its digits is divible by 3
        query[i][j] += ((arr[j] - arr[i - 1]) % 3 == 0);
    }
}

Nota: funzionerà quando il numero di elementi ( Range ) è compreso in 3 * 10^3 . Altrimenti la deculazione di query[Range][Range] mostrerà l'errore di compilazione.

Se non riesci ancora a ottenere ciò che sta accadendo in quei loop, usa carta e penna per disegnare una tabella 2D e riempirla secondo il calcolo precedente. Allora avrai sicuramente una chiara intuizione :)