I got error with an input: [1, 2], k = 3.
I don't understand why the expected output is [2, 1]. I saw some solutions. They all did
'k = k % num.size()
'.
Why? What does that mean？
It might help to think of the array as a circle. Let’s say the array has length 5, and contains the elements: A = 1, 2, 3, 4, 5.
If k = 1
, then rotate our circle by 1 position, i.e., A’ = 5, 1, 2, 3, 4.
If k = 5
what happens? We rotate our circle 5 times, and we are back where we started.
This is like a 12-hour clock face. If you move the hour hand 12 places, then the hour hand is pointing at the same hour you began rotating from.
Going back to our array. If k = 6 (k > A.length)
, then that’s the same as rotating the entire array once, and then one more. So, A’ = 5, 1, 2, 3, 4
. This is the same as when k = 1
.
So, the expression:
k = k % nums.length
Says that rotating the array by k
times, is the same, as rotating it by k % nums.length
times.
Going back to our example using array length 5
, and k = 6
:
6 mod 5 == 1 mod 5
. This means rotating right by 6 is the same as rotating right by 1.
Check out these links on modular arithmetic.
http://betterexplained.com/articles/fun-with-modular-arithmetic/
http://www.artofproblemsolving.com/wiki/index.php/Modular_arithmetic/Introduction
http://mathworld.wolfram.com/Congruence.html