Anzahl von subarrays, wo die Summe der Ziffern ist teilbar durch K

Gegeben ein array, herauszufinden, wie viele solcher untersequenzen (nicht erforderlich zu sein zusammenhängenden) bestehen dort, wo die Summe der Elemente in diesem subarray ist teilbar durch K.

Ich weiß, ein Ansatz mit der Komplexität 2^n, wie unten angegeben. es ist wie die Suche nach alle nCi wobei i=[0,n] und überprüfen, ob die Summe ist teilbar durch K.
Bitte geben Sie Pseudo-Code sowas wie lineare/quadratische oder n^3.

static int numways = 0;
void findNumOfSubArrays(int  [] arr,int index, int sum, int K) {
        if(index==arr.length) {
                if(sum%k==0) numways++;
        }
        else {
                findNumOfSubArrays(arr, index+1, sum, K);
                findNumOfSubArrays(arr, index+1, sum+arr[index], K);
        }
}

Dieser Ansatz, die Sie erwähnt sieht mehr als brute-force-als divide-and-conquer, einfach nur sagen
Reduzieren Sie die original-array auf den Bereich [0 .. (k-1)] von modulo, dann verwenden Sie dynamische Programmierung, um die Anzahl der Kombination (eine dimension ist der modulo, die andere dimension ist die Anzahl der Elemente, die Sie haben summiert).

InformationsquelleAutor Puneet Jaiswal | 2012-08-02

2

Input - array A der Länge n und einer natürlichen Zahl k.

Den Algorithmus:
- Konstrukt array B: für jede 1 <= i <= n: B[i] = (A[i] modulo K).
Nun können wir verwenden dynamische Programmierung:

Definieren wir D[i,j] = maximale Anzahl von sub-arrays - B[i..n], dass die Summe Ihrer Elemente modulo k entspricht j.

1 <= i <= n.
0 <= j <= k-1.

D[n,0] = if (b[n] == 0), 2. Ansonsten, 1.

wenn j > 0 :

D[n,j] = if (B[n] modulo k) == j, als 1. Andernfalls 0.

for i < n und 0 <= j <= k-1:

D[i,j] = max{D[i+1,j], 1 + D[i+1, D[i+1,(j-B[i]+k) modulo k)]}.
- Konstruieren, D.
- Return D[1,0].
Gesamte Laufzeit: O(n*k)
- D[i,j] = maximum number of sub-arrays of - B[j..n] that the sum of its elements = j Einer der j ist i, ist es nicht?
- Ich verstehe nicht, Ihre Frage - ich vertrete die Start-sub-array und j repräsentieren die Summe der sub-array-wollen wir (modulo k natürlich).
- so ist das nicht ein typho dann? Sollte es nicht B[i..n]? :\
- Natürlich, Sie haben Recht, ich regele das jetzt. Dank
- sorry Jungs.. was ich meinte war untersequenzen nur.. so macht diese Arbeit für die untersequenzen ?
- Der obige Algorithmus ist für die untersequenzen.
- D[i,j] = max{D[i+1,j], 1 + D[i+1, |j-(B[i] modulo k)|]}. <- Das ist falsch. (Einfach zu überprüfen, nehmen K = 1 sollte die Antwort sein 2^n (oder 2^n - 1 wenn Sie nicht zulassen, dass der leeres array).) Die subarrays der B[i..n] summieren zu j (mod K) 1 sind. diejenigen, die keinen B[i] und 2. diejenigen, die dies tun. Offensichtlich die sets sind disjunkt, die subarrays der B[(i+1)..k] summieren zu j sind D[i+1,j] an der Zahl, und diejenigen, die verwenden B[i] sind in 1-1-Korrespondenz mit den subarrays der B[(i+1)..n] summieren zu j - B[i] (mod K). So D[i,j] = D[i+1,j] + D[i+1,(j-B[i]+K)%K]. Auch die Initialisierung ist falsch...
- D[n,0] = 1 (leeres array), D[n,B[n]] = 1, D[n,j] = 0 ansonsten (wenn B[n] = 0, dann D[n,0] = 2).
- Du hast Recht, danke.
- hi barak, können Sie schreiben Sie den code für diese arbeiten
- ich habe versucht den code aber es funktioniert nicht
InformationsquelleAutor barak1412
0

Eigentlich, ich glaube nicht, dass dieses problem wahrscheinlich gelöst werden, in O(n^3) oder sogar in polynomialer Zeit, wenn der Bereich von K und die Reihe von zahlen in der Reihe, ist unbekannt. Hier ist, was ich denke:

Betrachten Sie den folgenden Fall an: die N zahlen in arr ist so etwas wie

[1,2,4,8,16,32,...,2^(N-1)]

,

in dieser Art und Weise, die Summen 2^N "subarrays" (nicht erforderlich zu sein zusammenhängenden) von arr, ist genau der integer-zahlen in [0,2^N)

und Fragen, wie viele von Ihnen ist teilbar durch K ist äquivalent zu Fragen, wie viele der zahlen sind teilbar durch K in [0, 2^N).

Ich weiß, die Antwort kann unmittelbar ermittelt werden, wie (2^N-1)/K (oder so) in dem obigen Fall. Aber , wenn wir nur ein paar ( vielleicht 3? 4? - ) Nummern in arr zufällig, zu "Graben einige zufällige Löcher" in der perfekt-zusammenhängenden-integer-Bereich [0,2^N), das macht es sieht unmöglich zu berechnen, die Antwort ohne Umweg über fast jede Zahl in [0,2^N).

ok nur ein paar dumme Gedanken ... könnte Total falsch liegen.
- n ist hier die Länge des Arrays. Er bat um polynomieller Zeit für n, nicht für irgendeine andere Sache, die Sie erwähnt haben
- und mein Punkt ist genau: dieses problem kann nicht gelöst werden, die in polynomialzeit für n
- als Referenz können Sie sehen, das über DP-Lösung von barak O(n*k), was bedeutet, dass der Algorithmus hängt von der Größe K. Das ist ein Beispiel Pseudo-polynomial-Zeit, das ist nicht ein Algorithmus in polynomieller Laufzeit für n.
- Du hast Recht, aber wenn Sie davon ausgehen k eine Konstante ist, und n ist die Länge pf-array, der obige Algorithmus ist O(n). Wenn Sie definieren n als Größe der Eingabe, die oben genannten Algorithmus nicht polynomial.
InformationsquelleAutor lavin
0

Benutzen ein Hilfs-array A

1) Während der Einnahme von input, speichern Sie die aktuelle Gesamtsumme der entsprechende index (dieser führt in O(n)):
```
int sum = 0;
for (int i = 0; i < n; i++)
{
    cin >> arr[i];
    sum += arr[i];
    A[i] = sum;
}
```
2) nun,
```
for (int i = 0; i < n; i++)
    for (int j = i; j < n; j++)
        check that (A[j] - A[i] + arr[i]) is divisible by k
```
Dort gehen Sie: O(n^2)...
- Sub-Arrays sind nicht unbedingt zusammenhängend als OP erwähnt.
- also sagen Sie unter den 2^n subarrays nicht mehr als n^2 subarrays werden konnte teilbar durch k ?
- Ich sagte die soln für Subarray..., was u ppl reden, abt Teilfolge, so dass u müssen, um die Frage in einer besseren Weise.
- Vielleicht wird er verwendet einen falschen Begriff, aber er schrieb "nicht erforderlich zu sein zusammenhängenden".
InformationsquelleAutor Pragnya Sagar Choudhury

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.