Rotate by k, with a copy
Send each value straight to where it ends up. About 9 minutes.
Jump straight to where each value lands
Rotating right by one, k times over, repeats a lot of shuffling. Instead, work out where each value ends up and put it there directly: every value moves k boxes to the right.
If that goes past the end, it wraps round to the front, like the hands of a clock going past 12. A value 2 boxes from the end, moving 3 places, lands in box 1.
10 is in box 0. Two places to the right is box 2.
The remainder does the wrapping
The remainder operator is a clock for box numbers. Divide by the length and keep the remainder, and any number wraps back into the range of real boxes. In a row of 5, box "6" becomes box 1.
Rotating by the full length changes nothing, just as a clock that moves 12 hours shows the same time. So shrink k to its remainder first. And check for an empty array before dividing by its length.
n = len(nums)
if n == 0:
return nums
k = k % n
result = [0] * n
for i in range(n):
result[(i + k) % n] = nums[i]
return resultAn array of 4 values is rotated right by 6. Where does the value in box 3 end up?
- ABox 1
- BBox 9
- CBox 3
Show the answer
Box 1. Rotating by 6 is the same as rotating by 2 (6 minus a full turn of 4). Box 3 moves 2 along and wraps round to box 1.
Rotate by k
Rotate the list right by k places and return the result. You may build a new list. k can be larger than the length.
nums = [10, 20, 30, 40, 50], k = 2 → [40, 50, 10, 20, 30]
0 ≤ n ≤ 1,000 · 0 ≤ k ≤ 1,000,000