Skip to main content

Codility Lesson 2: Arrays CyclicRotation (Solution in Python)

Question: Given a list of length N, print the elements of the list A after K right cyclic rotations
Description of Input Data: 
1. N,K are integers in the range of [0,100]
2. Elements in A lie in the range of [-1000,1000]

Example: 
Input Data: A=[3,8,9,7,6], N=5, K=3
Expected output: [9,7,6,3,8]

Logic:
1. Elements in the list A need to be reordered according to the value of K and length of list A
2. K elements from the end of the list are the first to appear
3. The remaining elements in the same order are placed after the K elements from the end of the list

Psedo Code:
1. Check the length of the input list( length = 0 or length > K or length < 0)
2. If length = 0 output is []
3. If length > K: then the output is concatination of A[-K:],A[:-K]
4. If length < K: then the output is concatination of A[-(K%length) :], A[: -(K%length)]

https://codility.com/programmers/lessons/2-arrays/cyclic_rotation/
Let us use some test cases to understand the functioning of the code:
Test Case 1:
When length of the input list is less than K
Input List: A = [3,8,9,7,6], K=3
Step 1: Compare length of the list to value of K
Length of A = 5 < K=3
Step 2: Building the output which is concatenation of A[-K : ],A[ : -K]
Using this picture here, which represents how indices in python are for accessing elements are defined, the solution can be easily identified.
A[-K : ] = A[-3 : ] = [9,7,6] and A[ : -K] = A[ : -3] = [3,8]
Concatenation of A[-K : ] and A[ : -K] = Concatenation of [9,7,6] and [3,8] = [9,7,6,3,8]

Now since we know how to compute the solution, let us see how this is the solution to cyclic rotation of the list.
When K=1 the cyclic rotation of the list [3,8,9,7,6] = [6,3,8,9,7] - last element of the list is the first element after the rotation
When K = 2 the cyclic rotation of the list [3,8,9,7,6] = [7,6,3,8,9] - the last element of K=1 cyclic rotation output is the first element on this list
Similarly when K=3 the cyclic rotation of the list [3,8,9,7,6] = [9,7,6,3,8]

Test Case 2: When the length of the list is greater than value of K
From the understanding of cyclic rotation it is evident that once the value of K = length of the list the list will remain unchanged. We will use this fact to solve this test case.
Input List: A = [3,8,9,7,6] and K=18
Step 1: Compare length of list A to value of K
Length of A = 5 < K=18
Step 2: Compute the solution, which is concatenation of A[-(K%len(A)):] and A[:-(K%len(A))]
K%len(A) = 18%5 = 3
This means A[-(K%len(A)):] and A[:-(K%len(A))] = A[-(3):] and A[:-(3)]
So the solution as discussed above will be [9,7,6,3,8]
Logically speaking with K=length of the A or multiples of length of A the cyclic rotation output becomes the input list A itself hence for all values of K > length A finding the cyclic rotation output of K%len(A) is equvalent to the finding the cyclic rotation value of K > len(A).

PS: You can also access this code @
https://github.com/samhithachalla/codilitysolutions/blob/codility-python-solutions-with-%3C100-score/CyclicRotation.py

How did you like my solution? Do you have a better and elegant way of completing this codility test? Is there a way I can improve my articles? Comment and let me know. Hope I helped a bit in your preparation. Looking forward to your next visit. :) Like always..Dont forget to like, share and subscribe.

Comments

Post a Comment

Popular posts from this blog

Codilty Lesson 3: Time Complexity PermMissingElem (Solution in Python)

Question: Find the missing number in the list containing natural numhers to N+1 Description of input data: 1. List A contains all natural numbers except one and is of length N - [1,..,(N+1)] 2. All elemnts in A are distinct Eample: Input List: A =  [2,3,1,5], N=4 Output: 4 Logic: One way to do it is to sort the list A. Then compare the sorted list with incrementing numbers. There is an elegant way to do this with a little more mathematics involved. We know the sum of first n natural numbers is n(n+1)/2. It is given that all elements of the are distinct, that is they appear only once in that list. Input list A contains all natural  numbers ad has one number missing. If we subtract the the sum of elements in the list from the sum of N natural numbers we will get the number that is missing in the list. Pseudo code: Method 1: 1. Sort the list. Compare length of the list to the max value on the list. 2. if len(A)==max(A) then the missing numbe...
Post a Comment
Read more

Codility Lesson 2: Arrays OddOccurancesInArray (Solution in Python)

Question: Find the element in the array list that occurs odd number of times Description of input: All input lists will contain only one number that occurs odd number of times Example: input = [9,3,9,3,9,7,9] output = 7 Logic: 1. Sort the data set in ascending order 2. Check all the even indiced numbers in the list if they match the next element 3. In case they match that number(at the even index) is present even number of times, when the numbers dont match the number it means that the number(at the even index) occurs odd number of times Code flow or Pseudo Code: 1. Check for length of input list if length is 1 output is that number else go to 2 2. For even numbered index check the sorted list if the next element matches the number in this position 3. If it doesnot match we have the number which occurs odd number of times else we have to repeat step 2 with the next even index 4. If there is no match until the last even index then the number that has odd occurances ...
Post a Comment
Read more

What is a codility test?..and why do I need to take it?

Codility is a website designed for screening programmers. It caters to employers and job seekers/coding enthusiasts. The employers can avail a free trial and register to use the website as a testing platform for screening developers/software engineers and job seekers can use the lessons and challenges to improve coding skills. Since its established that codility is a technical recruitment site, let us understand what kind of tests they deliver? and which group of employers are most likely to use this site?   What are codility tests?  Codility tests are timed competitive programming questions used for developer/software engineer recruitment. They have a different levels of questions from basic to expert level. A typical test has three questions which have to be completed in the time specified. A test generally goes like this: First the website shows you how to use its interface for the test. Then a question along w...
Post a Comment
Read more