سوال ۶۲ کنکور ارشد علوم کامپیوتر ۱۴۰۵

This is the classic in-place cyclic-replacement (“juggling”) algorithm for a left rotation.

What a left rotation must do. Shifting the array $k$ places to the left sends the element at index $(j+k)\bmod n$ to index $j$; that is, the new value of $A[j]$ is the old $A[(j+k)\bmod n]$.

Third blank — the inner move. Following one cycle we repeatedly pull the next element back: $A[j] = A[(j+k)\bmod n], \qquad j \leftarrow (j+k)\bmod n.$ The index must be reduced modulo $n$, so the blank is $A[(j+k)\bmod n]$. Options 2–4 write $A[j+k]$ (or $A[(j+k)]$) with no $\bmod n$, which reads past the end of the array — eliminated.

Second blank — the inner stop test. We saved $\text{temp}=A[i]$. The cycle ends at the slot that must receive $\text{temp}$, namely index $(n+i-k)\bmod n=(i-k)\bmod n$ (the predecessor of $i$ in the cycle). Executing the body there would write $A[(i-k)\bmod n]=A[i]$, but $A[i]$ was already overwritten. Hence loop while $j \ne (n+i-k)\bmod n$, then fill that slot with $\text{temp}$ (fourth blank). Since $(n+i)\bmod n=i$, options 2 and 3 (j != (n+i) mod n) would never enter the inner loop — eliminated.

First blank — the outer stop test. The permutation $j\mapsto(j+k)\bmod n$ splits $\{0,\dots,n-1\}$ into $g=\gcd(n,k)$ cycles, with representatives $0,1,\dots,g-1$. The variable $\text{min}$ (started at $n$) records the smallest index actually stepped onto. The cycle through $0$ is exactly the multiples of $g$, so its smallest nonzero member is $g$; after the first cycle $\text{min}=g$, and later cycles only reach indices $\ge g$. Thus the outer loop should run while $i < \text{min}$ (i.e. $i=0,1,\dots,g-1$). i > min (options 2, 4) is backwards — eliminated. The outer loop advances with $i = i+1$.

Quick trace ($n=6,\ k=2,\ g=2$).

• $i=0$: $A[0]\!\leftarrow\!A[2]$, $A[2]\!\leftarrow\!A[4]$, stop at $j=4$, set $A[4]=\text{temp}$; now $\text{min}=2$.
• $i=1<2$: $A[1]\!\leftarrow\!A[3]$, $A[3]\!\leftarrow\!A[5]$, set $A[5]=\text{temp}$.
• $i=2$ is not $<\text{min}=2$ → stop. All six elements are rotated in $\Theta(n)$ time, in place.

Every blank matches option 1.

Exam trick: In cycle-following rotation remember two things — every index is taken $\bmod n$, and the number of independent cycles is $\gcd(n,k)$. Here $\text{min}$ is just a clever way to discover $\gcd(n,k)$ on the fly.