Označimo skup ~\{1, 2, \ldots, N\}~ sa ~[[N]]~. Posmatrajmo dodele vrednosti za ~i = 0~ i definišimo dve funkcije

• ~f : [[N]] \rightarrow [[N]]~, takva da je ~a'_j = f(a_j)~, gde je ~a'_j~ vrednost na poziciji ~j~ u nizu ~A~ nakon izvršavanja dodela vrednosti za ~i = 0~ a ~a_j~ je ta vrednost pre izvršavanja dodela.
• ~g : [[N]] \rightarrow [[N]], g(N) := 1; g(x) := x + 1, x \neq N~ ciklično pomeranje za jedno mesto ulevo.

Sada ćemo operaciju koju treba izvršiti na nizu ~A~ (za svako ~i \in \{0, 1, \ldots, N-M \}~ i za svako ~j \in \{0, 1, \ldots, M-1\}~) označiti sa ~z~, gde je ~z : [[N]] \rightarrow [[N]]~. Označimo sa ~z_i : [[N]] \rightarrow [[N]]~ operaciju na nizu ~A~ koja odgovara izvršavanju unutrašnje for-petlje (po ~j~) za dato fiksno ~i~. Jasno je da važi: ~z = z_{N-M} \circ z_{N-M-1} \circ \ldots \circ z_0~. Ključna ideja je to što ~z_i~ možemo zapisati u obliku ~z_i = g^{-i} \circ f \circ g^i~. Ovo važi zato što preslikavanjem ~g^i~ "rotiramo" niz u takvu poziciju da element koji je bio na poziciji ~i~ je sada na poziciji ~0~. Nakon toga primenjujemo dodelu vrednosti sa ~f~ i ponovo rotiramo niz u kontra smeru za ~i~ mesta.

Ako zatim proširimo izraz za ~z~ i skratimo susedne parove ~\ldots g^{i} \circ g^{-(i-1)} \ldots~ ostaje nam ~z = g^{-(N-M)} \circ (f \circ g)^{N-M} \circ f~, odnosno, kraće ~z = g^{-k} \circ (g \circ f)^k~, gde smo uveli oznaku ~k := N-M+1~. Kako se ~g^{-k}~ lako računa kao desna rotacija za ~k~ mesta, ako uvedemo oznaku ~h := g \circ f~ ostaje nam da izračunamo ~k~-ti stepen ove funkcije.

Da bismo za svako ~i~ pronašli vrednost ~h^k(i)~ konstruišemo graf sa čvorovima ~\{1 \ldots N\}~ i usmerenim granama ~\{x \rightarrow h(x), x \in [[N]]\}~. Kako je usmeren, konačan i iz svakog čvora izlazi tačno jedna grana, komponente povezanosti (posmatrajući graf kao neusmeren) izgledaju kao ciklusi sa stablima čiji je tačno jedan čvor deo ciklusa (primetiti da kako je moguće da ~h(i) = i~ postoji mogućnost da ciklus sadrži samo jedan čvor). Usmerenje grana u ciklusu mora biti takvo da je ciklus i u usmerenom grafu, dok usmerenje grana u stablima mora biti takvo da je ulazni čvor bliži ciklusu od izlaznog.

Obilazeći svaku komponentu povezanosti (posmatrajući graf kao neusmeren) u njoj pronalazimo ciklus za čiji svaki čvor nalazimo ~h^k(i)~ kao ~c((id(i) + k) \mod d)~ gde je ~d~ dužina ciklusa koji sadrži čvor ~i~, ~idx(x)~ daje redni broj čvora ~x~ u ciklusu dok ~c(x)~ označava ~x~-ti čvor na tom ciklusu. Za "početak" ciklusa možemo izabrati proizvoljan čvor. Zatim _dfs_ obilaskom, kroz stabla povezana sa tim ciklusom, unazad (suprotno usmerenju grana) za svaki čvor ~i~ čiji je otac u stablu obilaska ~o_i~ računamo ~h^k(i)~ ili kao prethodnika čvora ~h^k(o_i)~ u ciklusu ukoliko je ~i~ na rastojanju od ciklusa manjem od ~k~ ili kao sina čvora ~h^k(o(i))~ u stablu obilaska u čijem podstablu se nalazi čvor ~i~. Ovog sina možemo naći tako što održavamo niz koji odgovara steku čvorova tokom _dfs_-a i uzimanjem ~k~-tog prethodnika trenutnog čvora.

Na kraju potrebno je samo izračunati traženu vrednost, znajući vrednosti niza ~A~ nakon svih dodela vrednosti.

• Vremenska složenost algoritma ~O(n)~
• Prostorna složenost algoritma ~O(n)~