AskSia

Plus

method RotateRight(a: array) requires a.Length > 0 modifies a ensures forall i :...

Apr 15, 2024

method RotateRight(a: array) requires a.Length > 0 modifies a ensures forall i :: 1<= i < a.Length ==> a[i] == old(a[(i-1)]) ensures a[0] == old(a[a.Length-1]) { var n := 1; while n != a.Length invariant 1 <= n <= a.Length invariant forall i :: 1 <= i < n ==> a[i] == old(a[i-1]) invariant a[0] == old(a[n-1]) invariant forall i :: n <= i <= a.Length-1 ==> a[i] == old(a[i]) { } a[0], a[n] := a[n], a[0]; n := n + 1; }

python

Explanation

The RotateRight function takes an array and rotates it to the right by one position. The last element becomes the first, and all other elements move one position to the right. The main function tests this behavior with two use cases.

Step-by-step Instruction

▪

Check if the array length is greater than 0 to proceed with the rotation

▪

Store the last element of the array before shifting the elements

▪

Use a for loop to shift all elements to the right by one position

▪

Place the last element into the first position of the array

▪

Return the modified array after the rotation

▪

Define the main function to test the RotateRight function with specific use cases

▪

Use assertions to verify that the RotateRight function behaves as expected

▪

Call the main function to execute the tests

Time Complexity

The time complexity of the RotateRight function is O(n) because it involves a single loop over the array, where n is the length of the array.

Space Complexity

The space complexity is O(1) because the rotation is done in place and no additional space is used proportional to the input size.