Solution to Cyclic-Rotation by codility

9 Feb

February 9, 2016 Sheng 33

Question: https://codility.com/demo/take-sample-test/cyclic_rotation/

Question Name: Cyclic-Rotation or CyclicRotation

With Python’s syntactic sugar, the solution is pretty short.

def solution(A, K):

# write your code in Python 2.7

if len(A) == 0:

return A

K = K % len(A)

return A[-K:] + A[:-K]

Well, kind of too easy. ~~Let’s try a C++ solution to demo the details better.~~

Thanks to @micropentium6, the original C++ solution is ugly and bad. Please refer to the solution from @micropentium6. Also another Python solution with the same method as @micropentium6’s can be found in an older post.

33 Replies to “Solution to Cyclic-Rotation by codility”

With all due respect, your C++ solution is still like Python tricks. By pushing back, the vector is extended through newly allocated space. You can, actually, do this in place with or without vector.

#include <vector>

using namespace std;

static inline void swapElems(vector<int> &A, int start, int end)

{

int tmp = 0;

while (start < end)

{

tmp = A[start];

A[start++] = A[end];

A[end--] = tmp;

}

vector<int> solutionCyclicRotation(vector<int> &A, int K)

{

int len = A.size();

if (0 == len || 0 == K)

return A;

K = K % len;

swapElems(A, len - K, len - 1);

swapElems(A, 0, len - K - 1);

swapElems(A, 0, len - 1);

return A;

}

Sheng says:
February 14, 2016 at 9:58 pm
I see~ I forgot this classic algorithm, which was mentioned in some old post. I was in the world of Python 🙂
Reply
- mallesh says:
  June 13, 2018 at 9:00 am
  hi sheng,
  your code output is this:
  INPUT: Array = [3, 8, 9, 7, 6]
  k = 3
  OUTPUT:[3, 9, 9, 7, 9, 3, 9]
  Reply
  - Sheng says:
    June 19, 2018 at 3:26 pm
    I cannot understand your statement. The code should work.
    Reply

#include

vector solution(vector &A, int K) {

// write your code in C++11 (g++ 4.8.2)

if (A.size() == 0) return A;

int len = A.size();

K %= len;

rotate(A.begin(), A.begin()+len-K, A.end());

return A;

}

Sheng says:
February 15, 2016 at 5:17 pm
The rotate function is missing~
Reply
- Sebastien says:
  April 3, 2018 at 6:09 am
  It is a standard function:
  http://en.cppreference.com/w/cpp/algorithm/rotate
  Reply
  - Sheng says:
    April 3, 2018 at 12:44 pm
    Thanks for pointing it out 🙂
    Reply

Javascript Solution

function solution(A, K) {

// write your code in JavaScript (Node.js 4.0.0)

// https://codility.com/demo/results/trainingGPNDGH-W42/

if (A.length !== 0){

var i=0, p;

while (i<K) {

p = A.pop();

A.unshift(p);

i++;

}

return A;

}

Results RotateArray(int A[], int N, int K) {

Results result;

int *temp = (int *)malloc(sizeof(int) * N);

for (int i = 0; i < N; i++)

{

temp[i] = A[i];

}

result.A = temp;

result.N = N;

for (int i = 0; i < N; i++)

{

int result_index = (i + K) % N;

result.A[result_index] = A[i];

}

return result;

}

My Javascript solution:

function solution(A, K) {

// https://codility.com/demo/results/trainingE3Y6TU-Q79/

while(A.length && K > 0) {

A.unshift(A.pop());

K--;

}

return A;

}

juan says:
September 7, 2016 at 6:48 am
Excelente!!, clean and straighfoward!
Reply

Here is what I came up with for a C# solution. It scored 100% on Codility:
https://codility.com/demo/results/training4T4DUN-KVN/

public int[] solution(int[] A, int K) {

if(K == 0 || A.Length == 0)

return A;

int[] res = new int[A.Length];

int len = A.Length;

for(int i = 0; i < len; i++)

{

if(i < (K%len))

res[i] = A[(len - (K%len))+i];

else

res[i] = A[System.Math.Abs((K%len)-i)];

}

return res;

}

cfrm says:
July 30, 2016 at 6:57 pm
Hello, I am trying to understand your solution and I have to question that I do not find the logic. Please could illustrate me about it or where I can read more details about your code.
The questions are comment on the solution. Thank you in advances
def solution(A, K):
# write your code in Python 2.7
if len(A) == 0:# why do you equal to cero len(A)?
return A
K = K % len(A)# Why do you module K % len(A)
return A[-K:] + A[:-K]
Reply
- Sheng says:
  August 11, 2016 at 8:51 pm
  Hello, they are mostly some mathematic issues.
  >> why do you equal to cero len(A)?
  A: handle the special case. Otherwise, when len(A) is 0, “K = K % len(A)” is illegal.
  >> Why do you module K % len(A)
  A: To make sure K is in the range of valid index (between 0 and len(A) – 1). The original question is rotation, so if we increase or decrease K by len(A), the result is totally the same.
  Reply
Karol Poczęsny says:
August 3, 2016 at 4:43 am
My C solution :
https://codility.com/demo/results/training9N28CG-KWS/
Reply

My C solution:

struct Results solution(int A[], int N, int K) {

struct Results result;

if(N) K = K % N; else K = 0;

int* B = malloc( sizeof(int) * N);

memcpy( &B[0], &A[N - K], sizeof(int) * K);

memcpy( &B[K], &A[0], sizeof(int) * ( N - K ) );

result.A = B;

result.N = N;

return result;

}

My Java solution (100%)

public int[] solution(int[] A, int K) {

int[] shiftedArray = new int[A.length];

for (int i = 0; i < A.length; i++) {

if (i + K >= A.length)

shiftedArray[(i + K) % A.length] = A[i];

else

shiftedArray[i + K] = A[i];

}

return shiftedArray;

}

Do we really need to shift array n times ? Instead we only need to figure out what is the index of the array would become the first element of new array, and then copy old array to new array. The following are my java solution.

class Solution

{

public int[] solution(int[] a, int k) {

if (a.length == 0){

return a;

}

int modular = k % a.length;

int index = a.length - modular;

int newArray[] = new int[a.length];

System.arraycopy( a, index, newArray, 0, a.length - index);

if (index > 0){

System.arraycopy( a, 0, newArray, a.length - index, index);

}

return newArray;

}

Sheng says:
August 28, 2016 at 8:11 pm
No, n-times shift is totally a waste. FYI, your solution needs additional O(N) space, which is not necessary. Please refer to @micropentium6 solution.
Reply

Lucian says:
September 28, 2016 at 12:06 pm
this scored 100% too
Reply
- Sheng says:
  September 29, 2016 at 11:09 pm
  Please read the “Guideline for Comments” in the right column first to post code. Thanks!
  Reply
Alok says:
December 22, 2016 at 11:11 pm
My Python solution
1
2
3
4
5
6
from collections import deque
def solution(A, K):
    # write your code in Python 2.7
    new_list = deque(A)
    new_list.rotate(K)
    print(list(new_list))

Reply

My soulition in php, got 100%:

function solution($A,$k) {

$shiftedArray = array_fill(0, count($A), NULL);

echo count($shiftedArray);

for ($i=0; $i<count($A); $i++) {

if ($i+$k>=count($A)) {

$shiftedArray[($i+$k)%count($A)]=$A[$i];

} else {

$shiftedArray[$i+$k]=$A[$i];

}

return $shiftedArray;

}

Hi Ahmed,
Cannot we use array functions to get the solution?

function solution($A, $K) {

if(count($A) == 0){

return $A;

}

for ($i=0; $i<$K; $i++){

$v = array_pop($A);

array_unshift($A, $v);

}

return $A;

}

My C++ solution

vector<int> solution(vector<int> &A, int K) {

// write your code in C++14 (g++ 6.2.0)

if (A.empty()) return A;

for (int i=0;i<K;i++)

{

A.insert(A.begin(), A[A.size()-1]);

A.pop_back();

}

return A;

}

Tan says:
June 10, 2018 at 11:50 am
My Solution (Python)
1
2
3
4
5
6
def solution(A, K):
    N = len(A)
    B = [0]*N
    for i in range(N):
        B[i] = A[ (i-K) % N]
    return B

Reply

My C# Code 100% works

public static int[] RotateArray(int[] A, int K)

{

//check condition

int N = A.Length;

if (N < 0 || N > 100) return A;

if (K < 0 || K > 100) return A;

if (K == 0) return A;

//new array

var B = new int[N];

for (int i = 0; i < N; i++)

{

// check item

var item = A[i];

if (item < -1000 || item > 1000) return A;

int newIndex = i + K;

int left = K%N;

while(newIndex > N-1)

{

newIndex -= N;

}

// simple swap index not value

B[newIndex] = item;

}

return B;

}

Here is python solution using Reversal Algorithm:

def solution(A,K):

return reverse(reverse(A[0:len(A)-K])+reverse(A[len(A)-K:len(A)]))

def reverse(A):

s=0

e=len(A)-1

while (s<e):

A[s],A[e] = A[e],A[s]

s+=1

e-=1

return A

reverse(str_arr)

def solution(A, K):
    # write your code in Python 3.6
    x = 1
    while x  0:
        A.insert(0, A[-1])    
        x += 1
        A.pop(-1)
    return(A)

This was my answer, for your reference. JS

function cyclicRotation(A, K){

K = K % A.length;

let startCut = A.length - K;

if(A.length === 0 || K<=0)

return A;

return [...A.slice(startCut, A.length), ...A.slice(0, startCut)]

}

My VB solution. Bizarre there isn’t a more straightforward way to get array length.

Private Function solution(A As Integer(), K As Integer) As Integer()

' write your code in VB.NET 4.0 (Mono)

dim size as integer

dim index as integer

size= ubound(A) + 1

dim B(size-1) as integer

dim diff as integer

dim rotate as integer

' don't calc if array of 1 or less

if size < 2 then

B=A

goto solved

end if

diff = K

' K should be remainder only, cut down to size

if K/size > 1 then

diff = K mod size

end if

' avoid calcs if new K and array size same

if diff = size then

B=A

goto Solved

end if

for index = lbound(A) to ubound(A)

rotate = index - diff

if rotate <0 then

rotate = rotate + size

end if

B(index) = A(rotate)

'console.writeline("rotation = "&rotate)

'console.writeline("array B= "&B(index))

Solved:

solution=B

End Function

Analysis summary
The solution obtained perfect score.

Binit Bhagat says:
October 3, 2021 at 12:13 am
My Python snippet (87%)
1
2
3
4
5
6
7
def solution(A, K):
    # write your code in Python 3.6
    n = len(A)
    if K>n:
        K %= n
    fi = n-K
    return A[fi:]+A[:fi]

Reply

33 Replies to “Solution to Cyclic-Rotation by codility”

Leave a Reply Cancel reply