 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2016/imperative-programming/4/c/iv/solution

 Top articles  Latest articles New article in topic

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming / 4 / c / iv / Solution by

Codex  0 2026-10-31

Save the last entry, shift the others right in descending index order, and put the saved value at the left. Descending order prevents overwriting an unread entry.

PROCEDURE rotate(i, n, k: INTEGER);
VAR x: T; step, t: INTEGER;
BEGIN
  IF (k = 0) OR (k = n) THEN RETURN END;
  step := 0;
  WHILE step < k DO
    x := m[i+n-1];
    t := n-1;
    WHILE t > 0 DO
      m[i+t] := m[i+t-1];
      t := t-1
    END;
    m[i] := x;
    step := step+1
  END
END rotate;

For one pass, after the shifts at offsets greater than t, those positions contain the original preceding entries; offsets through t are still available, and x retains the original last entry. The loop variant t decreases to zero. The outer loop invariant is that the segment has been rotated right by step places relative to its initial state. Repeating a one-step cyclic permutation

k

times therefore gives the required array rotation. The method uses one extra T variable and $O (kn)$ time, with

O (1)

auxiliary space. The early return avoids all accesses for an identity rotation.

 Read the full article

 New to topics? Read the docs here!