# Arrays: Left Rotation

# Arrays: Left Rotation

Hitscotty + 55 comments With my solution I used modular arithmetic to calculate the position of the each element and placed them as I read from input.

for(int i = 0; i < lengthOfArray; i++){ int newLocation = (i + (lengthOfArray - shiftAmount)) % lengthOfArray; a[newLocation] = in.nextInt(); }

antrikshverma2 + 1 comment Neat code , thanks Hitscotty !!

michellerodri247 + 0 comments The array is a part of the programming field. There are different topics related to this array destination wedding . The left rotation indicates the rotation of elements in an array. The rotation takes place in left wise. The rotation happens a single element at a time.

manishdas + 5 comments hmm.. I'm surprised that worked for you. This one worked for me:

str = '' length_of_array.times do |i| new_index = (i + no_of_left_rotation) % length_of_array str += "#{array[new_index]} " end puts str.strip

darwin57721 + 2 comments what is the starting value of your i? (i dont know ruby). d=2, n = 10. Because if it is 0, it would be (0+2)%10 = 2. What am I getting wrong?

manishdas + 1 comment The starting value of the i is 0. Looks like correct calculation to me. What result are you expecting?

darwin57721 + 0 comments ha, yeah i wasn't understanding right! I made it this way, that's why I was confused. rotated[(n+i-d)%n] = a[i]. Which is analogous to yours, but calculating the index in destination. Yours is more clear I think. Thanks!

Usernamer89 + 1 comment are you a mathematician? because i came out with a bit similar answer

dev1ender + 0 comments me too

jambekardhanash1 + 2 comments why do we need i? Can you please explain?

manishdas + 31 comments Based on current index (i), you need to generate new index. For example: let's say array = [1, 2, 3, 4] and k = 2, then after 2 left rotation it should be [3, 4, 1, 2] => 3 4 1 2 (space separated string output)

Now let's walk through my algorithm:

# Initial assignments: # array = [1, 2, 3, 4] # length_of_array = array.length = 4 # no_of_left_rotation = k = 2 # new_arr = Arra.new(length_of_array) # new_arr: [nil, nil, nil, nil] # NOTE: # length_of_array.times do |i| # is equivalent to # for(i = 0; i < length_of_array; i++) # Algorithm to calculate new index and update new array for each index (i): # new_index = (i + no_of_left_rotation) % length_of_array # new_arr[i] = array[new_index] # LOOP1: # i = 0 # new_index = (0 + 2) % 4 = 2 # new_arr[i = 0] = array[new_index = 2] = 3 # new_arr: [3, nil, nil, nil] # LOOP2: # i = 1 # new_index = (1 + 2) % 4 = 3 # new_arr[i = 1] = array[new_index = 3] = 4 # new_arr: [3, 4, nil, nil] # LOOP3: # i = 2 # new_index = (2 + 2) % 4 = 0 # new_arr[i = 2] = array[new_index = 0] = 1 # new_arr: [3, 4, 1, nil] # LOOP4: # i = 3 # new_index = (3 + 2) % 4 = 1 # new_arr[i = 3] = array[new_index = 1] = 2 # new_arr: [3, 4, 1, 2] # After final loop our new roated array is [3, 4, 1, 2] # You can return the output: # new_arr.join(' ') => 3 4 1 2

Hope that's clear.

glezin + 0 comments Crystal.

sarikaaa + 0 comments nice algo

bhavikpatel576 + 0 comments Great explanation! Thanks.

MobilityWins + 0 comments I am trying to understand this, but this is the first time I have seen value assignments that involve a val= val= anotherVal

I am not quite understanding how that is supposed to work, also what is "nil" and its purpose for an arrayjenish9599 + 0 comments Cool....

manavmehra96 + 0 comments Excellent Description!

mzancanella + 0 comments if the length of the array is = 3 then it seems it won't work.

p_callebat + 2 comments new_index = (i + no_of_left_rotation) % length_of_array;

seems incorrect. You will see the problem if you test, for example [1,2,3,4,5] and k = 2 .

I guess would be better:

new_index = (i + (lengthOfArray - no_of_left_rotation)) % lengthOfArray;

sfelde21 + 0 comments why?

sruthi_1401227 + 0 comments y ? its not working

supertrens + 3 comments Seems like this algorith only works for small number because when the array is big enough due to long looping period u will have system "timeout"

2017A7PS0931G + 2 comments I was facing the same problem.I gave several attempts but the issue couldn't be solved. Can you please tell me how to define a loop for a set of array with so many elements as such... :)

pawel_jozkow + 4 comments In java8 the problem was in String; You have to use more efficient StringBuilder instead; And of couse use only one loop to iterate over array;

here is my code snippet:

StringBuilder output = new StringBuilder(); for(int i = 0; i<n; i++) { b[i] = a[(i+k) % n]; output = output.append(b[i]).append(" "); }

arukas07 + 0 comments Thanks a lot!

Etcetra + 0 comments Thnx

Etcetra + 0 comments [deleted]d_p_sergeev + 0 comments Better to use linked list, so no need to LOOP fully:

val z = LinkedList(a.toList()) for(i in 0 until n) z.addLast(z.pollFirst())

sreetejayatam + 0 comments # include

void reverse(int *str,int length) { int start,end; for(start=0,end=length-1;start

`}`

} int main(){

`int size,nor; scanf("%d %d",&size,&nor); int *str=(int *)malloc(size*sizeof(int)); for(int i=0;i<size;scanf("%d",&str[i++])); reverse(str,size); reverse(str,size-nor); reverse(str+size-nor,nor); for(int i=0;i<size;printf("%d ",str[i++])); return 0;`

}

__raviraj__ + 3 comments # include

using namespace std; int main() { long int a[1000000],n,d,i,f; cin>>n>>d; for(i=0;i>a[i];

`for(int j=0;j<d;j++) { f=a[0]; for(i=0;i<n;i++) { a[i]=a[i+1]; } a[n-1]=f; } for(i=0;i<n;i++) cout<<a[i]<<" ";`

} //this is my code and im getting time out could u please solve

nsaikaly12 + 2 comments its because your solution is O(n^2) with the inner loop. Try and find an O(xn) solution and iterate over the whole array only once.

__raviraj__ + 0 comments [deleted]__raviraj__ + 1 comment i didnt get u

reddychintu + 0 comments O(n^2) means you have 2 for loops causing a greater time complexity

SBU3411348 + 0 comments static int[] rotLeft(int[] a, int d) { int j,i,p; for(j=0;j

Check with this you will get what is the mistake ypu did.

baymaxlim2204 + 0 comments My implementation of this in java didn't have this error.

joelvanpatten + 0 comments I was facing the same issue in PHP. My solution worked for 9 out of 10 test cases but timed out on one of them every time. You have to re-write the solution to be less memory intensive. In my case I was using array_shift() which re-indexes the arrays, so for large arrays it uses too much memory. My solution was to use array_reverse() and then array_pop() instead, because those methods don't re-index.

haroon_1993 + 0 comments This Does not suits for all entries if you make the rotation to more than 4 its fails

waseefakhtar + 0 comments Brilliant explanation!

mchandravadhana + 0 comments good explanation..working fine.

[deleted] + 0 comments nice algo...easy to understand ...thank u soo much

to_vishalsachde1 + 0 comments Adbsolute geeky, How did it appeared to your mind ?

lakshman1055 + 1 comment How to think like this ? Once the code is there I know its easy to understand.I want to know

**how**did you**know to use modulous**and how did you come up thinking that logic ?thanks in advance.

amrelbehairy88 + 1 comment Have you ever heard about Data Structure ? because if you do , you would probably heard about circular array.

I was able to solve the question because I'm knew about circular arrays , we use % + size of array to create a cirural array , then all you need to do is to complete the puzzle to solve the problem.

check this video, https://www.youtube.com/watch?v=okr-XE8yTO8&t=773s

tcjcastillo + 0 comments This is super helpful, thanks so much for sharing!

KivenL96 + 0 comments cool

hendradedisupri1 + 0 comments really run ?

sasuke_10 + 1 comment Great solution. Any tips on how to know if you need to use modulus in your algorithm? I solved this problem using 2 for loops...

mikehow1005 + 1 comment I figured it out by saying, I don't need to loop through this array over and over to know what the final state of the array should be. What I need to figure out is what the first element of the new array will be after I've rotated X amount of times. So if I divide the number of rotations (X) by the length of the array (lenArr) I should get the amount of times the array has been fully rotated. I don't need that, I need what the first element will be after this division operation. For that I need the remainder of that divison (the modulus). This is because after all of the full array loops are done, the remaining rotations determine what the first element in the new array will be.

So you take that remainder (modulus) and that's the first element's index in the old array. For example, 24 rotations in a 5 element long array means that the first element in the new array is in the 4th index of the old array. (24 % 5 = 4)

So rotate through [3, 4, 5, 6, 7] 24 times and the first element will be 7. So just take that and put it before the other elements. ([7. 3, 4, 5, 6])

Another good tip is always look for repeating patterns. It's a sign that you can simplify your code. The for loop method is just repeating the state of the array over and over: [3, 4, 5, 6, 7] [4, 5, 6, 7, 3,] [5, 6, 7, 3, 4,] [6, 7, 3, 4, 5,] [7, 3, 4, 5, 6,] [3, 4, 5, 6, 7] [4, 5, 6, 7, 3,] [5, 6, 7, 3, 4,]...

You only really need to know what's happening in the final few rotations, after the last full loop.

marwan_daar + 0 comments great explanation!

priteshbonde + 0 comments Nice explanation. helped me a lot. Thanks You

anilkumaryadav91 + 0 comments Awesome Explanation....Tq

anisharya16 + 0 comments thankyou so much, it helped a lot. but can you please tell how did you think about the new index position. what did you think?

zodiac_797 + 0 comments Great explanation!Thanks

g_panwar + 0 comments great way of explaining.big thank!

Narendr_Gadde + 0 comments Nice algo..

polaki + 0 comments Good Solution.

rakeshreddy5566 + 1 comment simple is peace

return arr[d:] +arr[0:d]

TamizhselvanR + 0 comments but im getting timed out if i do like this for 2 test cases

igor_atf + 0 comments Greatest explanation so far. Thanks!

itshiteshverma + 0 comments Well Explained !!

payaldev7910 + 0 comments Can you please also tell me the logic of right rotation .

srikaranb + 0 comments Thanks for the explanation

neha44 + 0 comments great explaination..

morrisontech + 0 comments i is a variable used to iterate through the loop, it generally represents the index of the array that is being referenced on a particular iteration of the loop.

abhash24oct + 0 comments Your code if for right rotation, and the explanation gave you right answer as the size was 4 and k =2 , so no matters you do left/right you will get same. For left it will be int newLoc= (n +(i-k))%n;

ang_7jd + 0 comments Array = {1,2,3,4,5} d = 4 Dosen't work for me

My Code :

for (int i = 0; i < a.Length; i++) { position = Math.Abs((i + (a.Length - d))% a.Length); newArray[position] = a[i]; }

ayushasthana025 + 0 comments nice algorithm manish

himaang + 3 comments I guess the logic fails if the input is as follows: 5-n 6-d 1 2 3 4 5

manishdas + 0 comments [deleted]phaniyelisi + 0 comments According to given constraint : 1 <= d <=n, d will not exceed n

hacknroll + 0 comments Even if there was no constraint, you could just do: k % n, and then apply the same logic.

zenmasterchris + 4 comments The question asks to shift a fully formed array, not to shift elements to their position as they're read in. Start with a fully formed array, then this solution does not work.

cmshiyas007 + 0 comments thats what me too thinking of..was wondering why the logic writte here was arranging the array on read...

andritogv + 1 comment That's exactly the point of the exercise. You have to rotate an already existing array.

avi_roychow + 0 comments Correct!

Turings_Ghost + 0 comments I noticed that right away. If the point was to produce printed output, then this is fine (and a lot of analysis works backward from output). But, as stated, one is supposed to shift an array, so this missed it.

aubreylolandt + 0 comments this could easily be modified though by creating another array of the same size:

vector b(n); for(int i = 0; i < n; i++) { b[i] = a[(i+k) % n]; } return b;

buzzaldrin + 0 comments I had the same idea! Just find the starting point of the array with the shift and count on from there, taking modulo and the size of the array into account.

denis_ariel + 1 comment (i + shift) % lenght Should be enough

robertgbjones + 0 comments Except that describes a right shift, and specification says a left shift. You might consider left shift to be negative shift, in which case you are correct mathematically, but I'd feel much more comfortable keeping the whole calculation in positive territory.

chrislucas + 3 comments modular arithmetic is cool. I solved that way too

for idx in range(0, _size): indexes[(idx - shift + _size) % _size] = _list[idx]

marwinko19 + 1 comment Can you please explain how that works?

chergik + 2 comments jericogantuangc1 + 0 comments Hello, where did this solution from? what should I study to be able to come up with solutions like this?

jattilah + 5 comments Looks a lot like my C# solution:

static int[] Rotate(int[] a, int n) { n %= a.Length; var ret = new int[a.Length]; for(int i = 0; i < a.Length; ++i) { ret[i] = a[(i + n) % a.Length]; } return ret; }

rodrigoramirez93 + 0 comments Perfect solution. Thanks for sharing

Aggasti + 1 comment Nice solution. You dont need:

n %= a.Length;

purshottamV + 1 comment This line usefull when n >= a.Length

malexj93 + 0 comments No it isn't. (i + n) % a.length and (i + n%a.length) % a.length are the same thing. It's only useful for the case where n is close to int maximum so that i + n overflows.

ronaldabellano + 0 comments Nice

ajaysharvesh_mp + 0 comments Could you please explain your solution..?

caiocapasso + 0 comments Here's another slightly different solution. I'm assuming it would be less performant, since it uses List and then converts it to Array, but I'm not sure how much more so.

`static int[] rotLeft(int[] a, int d) { var result = new List<int>(); for (int i = d; i < (a.Length + d); i++) { result.Add(a[i%a.Length]); } return result.ToArray(); }`

sidnext2none + 2 comments I agree modular arithmetic is awesome. But, simple list slicing as follows solves too ;)

def rotLeft(a, d): return a[d:]+a[:d]

asindhar + 0 comments I agree

antonio_gonzales + 0 comments Oh my goodness! You are the best!

jarvian + 2 comments what if newLocation becomes negative

diegobonales + 0 comments then you send it to the end of the array

Turings_Ghost + 0 comments The modulus operation always returns positive. If, as in Java, it really does remainder, rather than the mathematical modulus, it can return negative. So, depends on which language.

marakhakim + 2 comments What if lengthOfArray < shiftAmount? I think you should use abs value

digibluh + 0 comments there is a constraint that says there wont be negatives so it should be fine. if it wasn't given then use abs.

jattilah + 0 comments You deal with lengthOfArray < shiftAmount by using:

shiftAmount = shiftAmount % lengthOfArray;

If the array length is 4, and you're shifting 6, then you really just want to shift 2.

The constraints say that shiftAmount will always be >= 1, so you don't have to worry about negative numbers.

iAmBipinPaul + 0 comments Aweosme !!!

vovchuck_bogdan + 10 comments pretty simple in js:

a.splice(k).concat(a.slice(0, k)).join(' ')

cpbx12 + 0 comments [deleted]HackDaddy + 0 comments even simpler is a.splice(k).concat(a).join(' ')

ajkhatibi + 1 comment what does a represent?

flyinghorsedanc1 + 0 comments The array of initial values.

rags1981 + 0 comments [deleted]amezolma + 2 comments Did something similar in C#..

using System; using System.Collections.Generic; using System.IO; using System.Linq; class Solution { static string rotate(int rot, int[] arr) { string left = string.Join( " ", arr.Take(rot).ToArray() ); string right = string.Join( " ", arr.Skip(rot).ToArray() ); return right + ' ' + left; } static void Main(String[] args) { string[] tokens_n = Console.ReadLine().Split(' '); int n = Convert.ToInt32(tokens_n[0]); int k = Convert.ToInt32(tokens_n[1]); string[] a_temp = Console.ReadLine().Split(' '); int[] a = Array.ConvertAll(a_temp,Int32.Parse); // rotate and return as string string result = Solution.rotate(k, a); // print result Console.WriteLine(result); } }

merkman + 2 comments Or you can one line it with LINQ

Console.Write(string.Join(" ", a.Skip(k).Concat(a.Take(k)).ToArray()));

rahulbhansali + 1 comment While it is definitely elegant looking with a single line of code, how many times will this iterate over the array when performing 'skip', 'take' and 'concating' them? In other words, what's the complexity of this algorithm?

mihir7759 + 0 comments O(n)

jordandamman + 0 comments Any resources that explain how this works? I definitely see that it works, but say k is 5 in the first example and the array is 12345, it looks like we're skipping the whole array, then concatenating that whole array back to it with Take(5). What am I missing? Thank you for your time.

avi_roychow + 4 comments Can any one please tell me why the below code is timing out for large data set:

for(int j=0;j<k;j++) { for(int current=n-1;current>=0;current--) { if(current!=0) { if(temp!=0) { a[current-1]= a[current-1]+temp; temp= a[current-1]-temp; a[current-1]=a[current-1]-temp; } else { temp=a[current-1]; a[current-1]=a[current];//for the first time } } else//when current reaches the first element { a[n-1]=temp; } } } Console.WriteLine(string.Join(" ",a));

rishabh10 + 2 comments mine is also a brute force approach but it worked check it out if it helps you

import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { public static int[] arrayLeftRotation(int[] a, int n, int k) { int temp,i,j; for(i=0;i<k;i++){ temp=a[0]; for(j=1;j<n;j++){ a[j-1]=a[j]; } a[n-1]=temp; } return a; } public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int k = in.nextInt(); int a[] = new int[n]; for(int a_i=0; a_i < n; a_i++){ a[a_i] = in.nextInt(); } int[] output = new int[n]; output = arrayLeftRotation(a, n, k); for(int i = 0; i < n; i++) System.out.print(output[i] + " "); System.out.println(); } }

pateldeep18 + 0 comments int main(){ int n; int k; int temp1, temp2; scanf("%d %d",&n,&k); int *a = malloc(sizeof(int) * n); for(int a_i = 0; a_i < n; a_i++){ scanf("%d",&a[a_i]); } k = k %n; for(int a_i = 0; a_i < k; a_i++){ temp1 = a[0]; for(int i = 1; i < n; i++){ a[i-1] = a[i]; } a[n-1] = temp1; } for(int a_i = 0; a_i < n; a_i++){ printf("%d ", a[a_i]); } return 0; }

my code is the same as yours but i still time in test case 8, why is that?

not_nigel + 0 comments You're not wrong but this solution is inefficient. You're solving it in O(((n-1) * k) + 2n). The solution below is in O(2n).

private static void solution(int size, int shift, int[] arr) { int count = 0; for (int i = shift; i < size; i++) { System.out.print(arr[i]); System.out.print(" "); count++; } count = 0; for (int i = size - shift; i < size; i++) { System.out.print(arr[count]); if (i != size - 1) System.out.print(" "); count++; } }

ash_jo4444 + 2 comments I got a timeout error for TC#8 and #9 for the same logic in Python :(

Muthukumar_T + 1 comment i got time out for tc#8 in c why??????

val3rian + 0 comments Iterate over array only once

russelljuma + 0 comments No loops. Just split and reconnect. def rotLeft(a, d): b = [] b = a[d:len(a)] + a[0:d] return b

gdahis + 1 comment Because it is O(n*k), if you have a big n and a big k, it could timeout. See if you can think of an algorithm that would visit each array element only once and make it o(n). Also, is there any optimization you can make? For example: if k is bigger than n, then you don't need to do k rotations you just need to do k % n rotations and k will be much smaller, smaller than n. Example:

[ 1, 2, 3, 4, 5 ]

K=2, K=7=(1*5)+2, K=12=(2*5)+2, they are all equivant, leading the array to be:

[3, 4, 5, 1, 2]

mihir7759 + 0 comments [deleted]

Nitin304 + 1 comment My Solution :

public static int[] arrayLeftRotation(int[] a, int n, int k) { int[] b = new int[n]; for(int i=0;i<n-k;i++){ b[i] = a[k+i]; } int l = 0; for(int i=n-k;i<n;i++){ b[i] = a[l++]; } return b; }

hatem_ali64 + 1 comment [deleted]amit_feb06 + 1 comment with one for loop i have subitted the code

eddiecrochet1994 + 0 comments Can I ask how you managed that?

donald_thai + 0 comments Nice one! Didn't even think of that

thefonso + 0 comments in an actual interview they will ask you not to use splice or slice. had that happen ti me.

akimy + 0 comments pretty elegant solution

amandakoster + 0 comments [deleted]_e_popov + 1 comment indeed, forgot that

`end`

goes through the end of a sequence, so here is my solution`function rotLeft(a, d) { const index = d % a.length; return [...a.slice(index), ...a.slice(0, index)]; }`

vladimirvuj + 0 comments `function rotLeft(a, d) { return [...a.slice(d), ...a.slice(0, d)] }`

visbs58 + 0 comments nice one

douglascvas + 0 comments [deleted]jenish9599 + 0 comments i think that the new location = ((i + Shift)) % lenght of array

sidch95 + 0 comments godlike solution.

parthshorey + 0 comments this doesnt work if you shift by 3.

Paul_Denton + 1 comment Spoiler! You can do it even simpler: rotated[i] = a[(i + k) % n]. Also spoilers should be removed from the discussion or the discussion should only be available after solving. I will complain about this until its changed :P

rishabh10 + 0 comments wouldn't then space complexity be O(n)

jigarsnaik + 0 comments Very nice.

wjmillon + 0 comments @hitscotty what brought you to modular arithmetic for this solution?

chatpras + 0 comments what if shiftAmount is greater than length of array

gurdeeps158 + 0 comments your solution is cool but if you have an array as input then you are in trouble bcoz in that case you have space complexity of O(n) as you need an another array to store element in new place.. think..

[DELETED] + 1 comment [deleted]rishabh10 + 1 comment why do you use this approach if in a realtime env. this wouldn't be correct as you are just given the function to complete.

praveshjamgade + 0 comments rishabh10 can u please explain ??

dtoxecko + 0 comments It is not following the instructions. Sorry.

anushadandu + 0 comments Great Logic!! Thank you so much!!

rajeswariramasa1 + 0 comments can u pls expalin what is shiftAmount???

theshishodia + 2 comments Hey @Hitscotty! What will be the newLocation if you wish to do a right rotation?

sabujp + 0 comments right rotation : b[i] = a[(i-k)%n]

alexzaitsev + 0 comments Hey, guys

Here is a solution based on modular arithmetic for the case when k > n:new_index = (n + i - abs(k-n)) % n

(note:

*n - abs(k-n)*can be collapsed to a single number)ViNii + 0 comments This only work when you read directly from input. But in the question they have asked to do rotation operation only on Array, so your solution cannot be used for this problem.

sfelde21 + 0 comments I understand how this works, but how did you think of it?

ciceromoura13 + 0 comments [deleted]ro63rtD + 0 comments Worked like a charm! Thanks!

milindmehtamsc + 0 comments This will also fail when my shiftAmount = 7 and lengthOfArray = 3, in short lengthOfArray is less than shiftAmount. In this case we can use Math.abs(). for(int a_i=0; a_i < n; a_i++){ int new_index = Math.abs((a_i + (lengthOfArray - shiftAmount))) % lengthOfArray ; a[new_index] = in.nextInt(); }

AshrafShekh + 0 comments Superb man.....

codextj + 1 comment That's nice but its kinda cheating :)

mihir7759 + 1 comment It's not cheating exactly. Using the same method you can even rotate the array, instead of printing the array just give the values of the array to a new array.

codextj + 0 comments I was nitpicking,

*I thought of the same soln at first but then changed my mind;*As the question was

**GIVEN an array**..so if this was an interview there is this constraint that your array is already populated with the elements.btw r u 14 ? its great to see my young indian frnds indulging in programing

pul_k3333 + 0 comments Well done! I did it by finding the correct number for the index, rather than the new position of a given number:

for (int i =0; i < n; i++){ int num = a[((n + k) % n + i) % n]; System.out.print((num) + " "); }

gptran96 + 0 comments very good, thanks!!!

96rishu_nidhi + 1 comment can u please elaborate some more about your code as i dont have much knowledge about modular maths

mihir7759 + 0 comments Have I used modulo in my code? I really forgot what have I written if you could show me the code then I can elaborate :)

greengalaxy2016 + 0 comments the requirement is to take an array and left rotate the array d times. Your solution returns the correct result, but takes an integer one at a time.

venkataramanago1 + 0 comments what is in.nextInt() here.

c00301223 + 0 comments Thanks for sharing this code it really helpped. I felt the constraints were to be includes by ifstatements but after viewing your code I was able get it. I have a small suggestion, would it improve the code if one were to seperate the (LengthOfArray - ShiftAmount) part into a variable and then reuse it since its kind of a constant value. Once again kudos.

rinshukr3 + 0 comments what is the use of in.nextInt(),will u plz explain me.

t_hacker + 0 comments Neat code, the only possible optimization is extra space used. even for a single rotation on say 1 million elements, the algo is greedy on space and will create 1 million auxilary elements.

moazashraf007 + 0 comments Brilliant

riyaz_rayyan07 + 0 comments what is in.nextInt() which language is that did you create another scanner object of in can you be more specific?

golzar_mohammad + 0 comments Very celever! thanks.

rakeshreddy5566 + 0 comments reverse it

arr1=a[0:d]

arr2=a[d:]

return arr2+arr1

ZeoNeo + 0 comments It's easy when you directly read them from system input. Try to make it work on already stored array. That's what problem statement says. It gets tricky and interesting after that to solve it in o(n) without extra memory.

i.e. // Complete roLeft function

My solution

`private static int getIncomingIndex(int index, int rotations, int length) { if(index < (length - rotations)) { return index + rotations; } return index + rotations - length; }`

`// Complete the rotLeft function below. static int[] rotLeft(int[] a, int d) { int rotations = d % a.length; if(a.length == 0 || a.length == 1 || rotations == 0) { return a; } if( a.length % 2 == 0 && a.length / 2 == rotations) { for(int i =0 ; i < a.length / 2 ; i++) { swap(a, i, i + rotations); } } else { int count = 0; int i = 0; while(true) { int dstIndex = getIncomingIndex(i, rotations, a.length); swap(a, i, dstIndex); i = dstIndex; count++; if(count == a.length - 1) { break; } } } return a; }`

madhanmohansure + 1 comment nice code tq

ZeoNeo + 0 comments Welcome.

scweiss1 + 1 comment The part I'm missing here is why use a loop (O(n)). Can't you take the array and find the effective rotation based on the shift amount (using the same modular arithemetic you're doing? (Which is now O(1) since the length of the array is a property)

function rotLeft(a, d) { //calculate effective rotation (d % a.length) let effectiveRotation = d % a.length; // split a at index of effective rotation into left and right let leftPortion = a.slice(0, effectiveRotation); let rightPortion = a.slice(effectiveRotation); // concat left to right return rightPortion.concat(leftPortion) }

ZeoNeo + 0 comments Can you explain how this is O(1) ? Please read about how slice and concatenation implemented in the language you are using. Also it uses extra memory.

kskrish75 + 0 comments vera level..!

silverdust2695 + 0 comments Why would you loop for every element when in essence the rotation operation is nothing but just a rearrangement of the array elements in a specified fashion?

calatayud_zepeda + 0 comments [deleted]007sophie + 0 comments helps a lot

nikolay_nedkov + 0 comments Verry Good!

diliniwis + 0 comments I saw this answer in stackoverflow too.. Please be kind enough to explain this.

Thanks

qzhang63 + 13 comments Python 3

It is way easier if you choose python since you can play with indices.

def array_left_rotation(a, n, k): alist = list(a) b = alist[k:]+alist[:k] return b

kevinmathis08 + 10 comments Yeah index slicing FTW, here was my 1-liner in definition, lol:

def array_left_rotation(a, n, k): return a[k:]+a[:k] n, k = map(int, input().strip().split(' ')) a = list(map(int, input().strip().split(' '))) answer = array_left_rotation(a, n, k); print(*answer, sep=' ')

Lord_krishna + 1 comment is that scala?

domar + 0 comments It's Python 3

aniket_vartak + 1 comment you dont need to pass n to your function, right..

michael_bubb + 2 comments I agree - I ended up not using 'n' (Python):

def left_shift(n,k,a): for _ in range(k): a.append(a.pop(0)) print(*a)

unitraxx + 1 comment Obviously this solves the problem, but is a terrible solution. Pop is an O(N) operation. So your solution becomes O(K*N). This should be done in O(N) total time complexity. You do have the space requirement of O(1) correct. All the standard solutions have a O(N) space complexity.

asfaltboy + 1 comment True. However, it becomes an elegant solution if we use collections.dequeue instead of list. Double ended queues have a popleft method, which is an O(1) operation:

def array_left_rotation(a, n, k): for _ in range(k): a.append(a.popleft()) return a

More info: https://wiki.python.org/moin/TimeComplexity#collections.deque https://docs.python.org/3/library/collections.html#collections.deque

AffineStructure + 1 comment They have rotate built into the deque

def array_left_rotation(a, n, k): a = deque(a) for i in range(k): a.rotate(-1) return a

josegabriel_st + 0 comments You have O(n) in:

a = deque(a)

In order to avoid this, you should use a deque from the beginning like:

from collections import deque def array_left_rotation(a, n, k): a.rotate(-k) n, k = map(int, input().strip().split(' ')) a = deque(map(int, input().strip().split(' '))) array_left_rotation(a, n, k); print(*a, sep=' ')

And

**array_left_rotation**only takes O(k) instead of O(n).Note that

**a**is pased by reference, so there is no need to return anything, but this could be an issue for some user cases, for this particular problem, it works.

navi_srm + 0 comments def array_left_rotation(a, n, k): return (a[k:] + a[:k])

ansimionescu + 1 comment `k -> k%n`

frostje + 0 comments k%n handles any range of shifts, but the problem specifies n < k so you can just use k in this case

loks30 + 1 comment This logic fails when k>n.

madhuvasu7 + 0 comments for that, do:

k = k%n

chrislucas + 0 comments Nice, only one line was added

marwinko19 + 0 comments Perfection. Short, simple, & clean.

ahmettortumlu25 + 0 comments hmm nice....

aliie62 + 0 comments It's so smart! well done:)

toaa_kama2354 + 0 comments Can you please explain how (a[k:]+a[:k]) is working?

jae_duk_seo + 0 comments Damn this is super impressive.

todor_90 + 0 comments [deleted]domar + 1 comment Pretty smart, but are you sure you are not copying the

`k`

th eleement, in ruby it would be:def array_left_rotation(a, k) a[k..-1] + a[0...k] end

In ruby,

`...`

means excluding the right number.kevinmathis08 + 1 comment Yes both qzangs and my answer is correct. In python index slicing (

*indices[start:stop:step]*), works like so...We will begin with the index specified at start and traverse to the next index by our step amount (i.e. if step = 2, then we jump over every other element, if step = 3, we jump over 2 elements at a time). If step is not specified it is defaulted to 1. We continue steping from our start point until we come to or exeed our stop point. We do NOT get the stop point, it simply represents the point at which we stop.

I love Python :)

domar + 0 comments Ok, so it's exclusive by default in Python, interesting.

JXSan + 0 comments Haha that's what I did, got to love Python !

pandasagar + 0 comments thanks. makes more sense

RVK5233 + 0 comments Thanks ....... Its working and simple to learn

crassus88 + 0 comments I think 'k' should be allowed to be greater than 'n'':

def array_left_rotation(a, n, k): d = k % n ret_arr = a[d:] ret_arr.extend(a[:d]) return ret_arr def array_left_rotation(a, k): d = k % len(a) return a[d:] + a[:d]

MaxNRG + 0 comments def array_left_rotation(a, n, k): return a[k:] + a[:k]

burakozdemir32 + 0 comments What about if 'k' is greater than 'n'? You should use modular arithmetic to get actual rotate count.

actual_rotate_count = k % n

Then your solution would work for every k values.

sdasara95 + 0 comments This won't work if the number of rotations is greater than the length of the array. The test cases must have all had d < n I guess This is a modification that I did so it satisfies the above case too.

def rotLeft(a, d,n):

`rem = d%n`

`new = a[rem:]+a[:rem]`

`return new`

rox_gelsy + 0 comments return a[k:] + a[:k]

liorkatzz + 0 comments Great answer, you just need %size_of_list for cases the k is greater than the size of the list

jhaaditya14 + 2 comments I am getting request timeout for test case 8... anyone with same problem?? or anyone knows the solution??

vabanagas + 1 comment The test case is a large array with a large amount of shits. If your algorithim is not effecient than it will time out.

Array size: 73642 Left shifts: 60581

nie_cyril + 0 comments I agree that it timesout if the algorithm is not efficient enough. Instead of relying on rudimental loops, try using a linked list which simplifies its complexity significantly to O(dn).

shilpaJayashekar + 0 comments If u are using javascript, this will work var b = a.splice(0, d); a = a.concat(b);

chenyu_zhu86 + 1 comment Python index slicing makes this trivial :D

def array_left_rotation(a, n, k): return a[k:] + a[:k]

varellap + 0 comments That's the simplest solution in Python!

darkOverLord + 5 comments I did it this way, in Java

public static int[] arrayLeftRotation(int[] a, int n, int k) { if (k >= n) { k = k % n; } if (k == 0) return a; int[] temp = new int[n]; for (int i = 0; i < n; i++) { if (i + k < n) { temp[i] = a[i + k]; } else { temp[i] = a[(i + k) - n]; } } return temp; }

vinaysh + 1 comment instead of if-else statement temp[i] = a[(i+k)%n]; would be enough.

Also this solution would take up extra memory(for temp).

shortcut2alireza + 2 comments Would you mind sharing your solution that does it in-place? Thanks

jacob0306 + 1 comment in case you need it! hope it help!

import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int k = in.nextInt(); int a[] = new int[n]; for(int a_i=0; a_i < n; a_i++){ a[((n- (k%n))+a_i)%n] = in.nextInt(); } for(int i = 0; i < n; i++) System.out.print(a[i] + " "); System.out.println(); } }

ngokli + 1 comment This is a good reason to start looping on the first element of the input, rather than the output.

But the problem statement does say you are "Given an array" (not a stream).

hackerrank_com23 + 3 comments Here's my in-place function implementation:

public static int[] arrayLeftRotation(int[] a, int n, int k) { // Rotate in-place int[] temp = new int[k]; System.arraycopy(a, 0, temp, 0, k); System.arraycopy(a, k, a, 0, n - k); System.arraycopy(temp, 0, a, n - k, k); return a; }

Angi29 + 0 comments [deleted]Angi29 + 0 comments idem, just a little variation : kifs

`static int[] rotLeft(int[] a, int d) { int length = a.length; int[] b = new int[length]; System.arraycopy(a, d, b, 0, length - d); System.arraycopy(a, 0, b, length - d, d); return b; }`

denis631 + 1 comment How is this in-place when you allocate a new array of size k.

venom1724 + 0 comments Indeed, its not in-place at all. Also its slow. If you are interested, here's an inplace c++ solution

void rotLeft(vector<int> &a, int d) { int c=a[d],ci=0,n=a.size(); a[d]=0; for(int i=n-1;i>=0;i--){ swap(a[ci],c); if(!c&&i) ci+=n-i+++i; ci=(n+ci-d)%n; } }

mohitgautam2k16 + 0 comments [deleted]123shuklaprasha1 + 0 comments why u have used that command of else please explain me

cc_insp + 0 comments I used the System.arraycopy() method which was used in the video tutorial. I'm wondering if this solution is more efficient or mine?

import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int k = in.nextInt(); int a[] = new int[n]; for(int a_i=0; a_i < n; a_i++){ a[a_i] = in.nextInt(); } a = leftRotation(n, k, a); for (int i=0; i<a.length; i++) { System.out.print(a[i]+" "); } } public static int[] leftRotation(int n, int k, int[] a){ int[] copy = new int[n]; System.arraycopy(a, k, copy, 0, (n - k)); System.arraycopy(a, 0, copy, (n - k), (n - (n - k))); return copy; } }

yash_97373 + 0 comments Is calculation really required ?

for(int i=k; i < a.length; i++){ System.out.print(a[i] + " "); } for(int i=0; i < k; i++){ System.out.print(a[i] + " "); }

danyim + 4 comments 2 lines of JS:

while(k-- !== 0) a.push(a.shift()) console.log(a.join(' '));

HeinousTugboat + 3 comments One line of JS, no looping:

console.log(a.concat(a.splice(0,k).join(' ')));

akimy + 0 comments I've the same solution. gj

main = () => { let [integersCount, rotations] = readLine().split(' ').map(Number) let array = readLine().split(' ').map(Number) while(rotations--) array.push(array.shift()) console.log(array.join(' ')) }

dsonemail + 0 comments [deleted]

noahlbw + 3 comments There is no need to do copying of data. The question is just to print out the values. The following code suffices, I think.

`int *b; int b_i; b = a + k; for(b_i = 0; b_i < n; b_i++) { if((int)(b - a) >= n) { b = a; } printf("%d ",*b++); }`

devesh23 + 0 comments I also thought the same. Even if the rotations are made subsequent we can have two pointers

*x*and*y*take care of the start of new array after rotations and end of new array after rotations. Then we can print from x to y.(Only in case of multiple query)marochm + 0 comments I don't think that's a valid assumption. The question is pretty clear about that: "perform left rotations

**ON THE ARRAY**.**THEN**print**THE UPDATED ARRAY**as a single line of space-separated integers."MohammedKadir + 1 comment Not sure about that. The instructions are two fold, and they distinguish between rotations and printing. I think it's expecting the values to physically shift.

*"perform left rotations on the array. Then print the updated array as a single line of space-separated integers."*aishwaryagaud17 + 0 comments [deleted]

mmicael + 2 comments In PHP:

$list = array_merge(array_slice($a, $k), array_slice($a, 0, $k)); echo implode(" ", $list);

quliyev_rustam + 0 comments Hi!

You are in right way, but in wrong code.

You need use this:

a, a)-a, 0, $k));

kuttumiah + 1 comment Hi,

For cases including shifts more than the array size this should work.

$actual_shift = $d % count($a); $list = array_merge(array_slice($a, $actual_shift), array_slice($a, 0, $actual_shift));

quliyev_rustam + 1 comment It is not necessary. By the hypothesis of the task shifts cant bo more than array size

kuttumiah + 1 comment Yeah, Thanks for the response. I missed that hypothesis.

In that case this shouldn't this be just fine?

`array_merge(array_slice($a, $k), array_slice($a, 0, $k));`

quliyev_rustam + 1 comment In this test, for "Tester 8", you need to use third argument for array_slice. Otherwise, an error is returned.

This is because for "Tester 8" uses a large array of transmitted values

kuttumiah + 1 comment According to the PHP documentation of

`array_slice`

third argument denotes the*length*of the slice.`array array_slice ( array $array , int $offset [, int $length = NULL [, bool $preserve_keys = FALSE ]] )`

If I do not pass third argument then it will be

`NULL`

by default. As a result the slice will be created until the end of the array. I believe there is nothing to do with the volume of the array. Moreover, without passing the third argument like I denoted in my previous comment I am having all the test cases passed.quliyev_rustam + 0 comments Moreover, without passing the third argument like I denoted in my previous comment I am having all the test cases passed.

It's very strange. But, yesterday, when I tested, it didnt work.

Yes, you are right! It have to be like you write!

zul110 + 2 comments C#:

Queue<int> inputs = new Queue<int>(a.ToList()); while(k-- > 0) { inputs.Enqueue(inputs.Dequeue()); } foreach(int input in inputs) { Console.Write(input + " "); }

StefanCFC + 1 comment Well done man. But can you just explain it how it works? Thank you btw.

zul110 + 1 comment Thank you Stefan :)

I created a queue of integers from the array, and enqueued its first integer back into it. I got the first integer by dequeuing the queue. I do this times the number of rotations given in the input, k.

In other words:

Dequeue() gives me the first element in the queue, which I then Enqueue(int) into the queue itself.This goes on until the number of rotations, k, becomes 0. I decrease k by 1 at each while cycle.

while(k-- > 0) { queue.Enqueue(queue.Dequeue()); }

Example:

Array: 1 2 3 4 5

k: 4

k = 4:

Dequeue: get [1]

Array: 2 3 4 5

Enqueue[1]: 2 3 4 5 1

k = 3:

Dequeue: get [2]

Array: 3 4 5 1

Enqueue[2]: 3 4 5 1 2

k = 2:

Dequeue: get [3]

Array: 4 5 1 2

Enqueue[3]: 4 5 1 2 3

k = 1:

Dequeue: get [4]

Array: 5 1 2 3

Enqueue[4]: 5 1 2 3 4

k = 0:

STOP

Hope it is clear :)StefanCFC + 0 comments Yeah it's clear! I had to draw the queue to understand what you've done :D Thank you again!

Freiling + 0 comments I had a very similar solution. Why did you return via a for-loop instead of returning the array?

`static int[] rotLeft(int[] a, int d) { Queue<int> z = new Queue<int>(a.ToList()); while (d-- > 0) { z.Enqueue(z.Dequeue()); } return z.ToArray(); }`

yildirim84 + 1 comment for(int i = 0; i < n; i++){ b[i] = a[(i+k)%n]; }

I guess this is the most primitive solution to understand.

Greydon + 0 comments for i in range(k): a.append(a.pop(0))

Sort 2011 Discussions, By:

Please Login in order to post a comment