We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

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.

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!

Awesome blog. I enjoyed reading your articles. This is truly a great read for me. I have bookmarked it and I am looking forward to reading new articles. Keep up the good work!.

if you guys want to start your own business. But don't have money to start your business.

you can start your business at a very low investment, by joining a multi level marketing company .if your want to know how to choose a rught company then click here it is a business which is easy to start and run with very low risk.

what does it mean. well it may surprise you but it is something that you already do every day, Multi Level Marketing simply means word-of-mouth advertising,or recommending something to someone. If you take a moment to think about it this is something that we all do on a regular basis, we refer friends to our favorite restaurants, movies and vacation spots.We refer books stores, doctors and any number of products that we like to people we know it's simply part of our nature.So the fact is we are all technically Multi Level Marketer,it's just who we are the difference is most of us don't get paid to do this.But some people do and they get paid very well.As you will learn in a moment they are compensated for far more than just their personal recommendations. for more info click here.

https://www.networkingmarketingnew.com/">9 tips for multi level marketing
In multi level marketing, many people come to earn money. Many people fall into this temptation, they will get a lot of money from here, they will not have to work here at all. You guys, let me tell you that without working here, you cannot earn money anywhere. Friends, let me tell you that

multi level marketing is a business that is exactly like a mountain.
If you want to dig it with a spoon, you will not be able to dig it all, nor will you be able to get it yourself with the help of ax. You will need JCB to find it. Similarly, in multi-level marketing too, you should get lots of tips and tricks, with the help of which you can dig the mountain or multi-level marketing.

If you work properly in multi-level marketing and keep developing your skills, then you will be able to earn a lot of money from here, but if you keep thinking in multi-level marketing, nothing has been done, and many more You get all the money here, you will waste your time here and you will not be able to earn anything. You have a lot of work here. Now work in the film part time, but for how long you are working, you will have to work with your mind.
In multi level marketing, there are some steps which are very important. You have to follow them everyday so that you can go far ahead in multi level marketing. In this post, I will tell you about the steps by doing them completely.You keep reading click here

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

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 array

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... :)

an inner loop will not cause his program to time out. I don't believe the variable n was ever initialized, so the loop is approaching a value of n that isn't defined.

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.

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 ?

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.

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.

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.

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;

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.

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.

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.

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.

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.

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();
}

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.

usingSystem;usingSystem.Collections.Generic;usingSystem.IO;usingSystem.Linq;classSolution{staticstringrotate(introt,int[]arr){stringleft=string.Join(" ",arr.Take(rot).ToArray());stringright=string.Join(" ",arr.Skip(rot).ToArray());returnright+' '+left;}staticvoidMain(String[]args){string[]tokens_n=Console.ReadLine().Split(' ');intn=Convert.ToInt32(tokens_n[0]);intk=Convert.ToInt32(tokens_n[1]);string[]a_temp=Console.ReadLine().Split(' ');int[]a=Array.ConvertAll(a_temp,Int32.Parse);// rotate and return as stringstringresult=Solution.rotate(k,a);// print result Console.WriteLine(result);}}

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?

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.

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

for(intj=0;j<k;j++){for(intcurrent=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));

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:

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

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..

Right rotation can be done by changing the '-' sign..
Use [(n+k+i)%n] one in scan function.. and also it is useful to keep in mind ,1 right roation=(n-1)left rotation..

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.

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();
}

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.

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.

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.

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;
}

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)

functionrotLeft(a,d){//calculate effective rotation (d % a.length)leteffectiveRotation=d%a.length;// split a at index of effective rotation into left and rightletleftPortion=a.slice(0,effectiveRotation);letrightPortion=a.slice(effectiveRotation);// concat left to rightreturnrightPortion.concat(leftPortion)}

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?

But isn't the whole point that you are not placing them as they come, the array is pre-populated and then rotate it. My solution is O(dn), not sure if there is anything better. Clearly I am not an algorithm guy (anymore)!

for (int i = 0; i < d; i++) {
int pop=a[0];
//shift left
for (int j = 1; j < a.length; j++) {
a[j-1] = a[j];
}
//push
a[a.length-1]=pop;
}

Excellent !!! I am new to problem solving. I had solved it via normal shifting using one for loop and one while loop. How did you arrive at this kind of solution?? Little bit of explanation as what you thought while solving this would help a lot.

If the number of rotations are greater than array length (I know it's less than array length which is given in the question, let us assume), then how would this formula change? BTW That's a great way to get the array indices without having to traverse the whole array

I was thinking to do the same but thought not gonna do this with arithmetic so I just looped twice.

let result = [];
for(let i = shiftAmount; i < array.length; i++){
result.push(array[i]);
}
for(let i = 0; i < shiftAmount; i++){
result.push(array[i]);
}
return result;

## Arrays: Left Rotation

You are viewing a single comment's thread. Return to all comments →

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

Neat code , thanks Hitscotty !!

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.

hmm.. I'm surprised that worked for you. This one worked for me:

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?

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

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!

are you a mathematician? because i came out with a bit similar answer

me too

Awesome blog. I enjoyed reading your articles. This is truly a great read for me. I have bookmarked it and I am looking forward to reading new articles. Keep up the good work!.

if you guys want to start your own business. But don't have money to start your business.

you can start your business at a very low investment, by joining a multi level marketing company .if your want to know how to choose a rught company then click here it is a business which is easy to start and run with very low risk.

Multi Level Marketing orMLM,

what does it mean. well it may surprise you but it is something that you already do every day, Multi Level Marketing simply means word-of-mouth advertising,or recommending something to someone. If you take a moment to think about it this is something that we all do on a regular basis, we refer friends to our favorite restaurants, movies and vacation spots.We refer books stores, doctors and any number of products that we like to people we know it's simply part of our nature.So the fact is we are all technically Multi Level Marketer,it's just who we are the difference is most of us don't get paid to do this.But some people do and they get paid very well.As you will learn in a moment they are compensated for far more than just their personal recommendations. for more info click here.

https://www.networkingmarketingnew.com/">9 tips for multi level marketing In multi level marketing, many people come to earn money. Many people fall into this temptation, they will get a lot of money from here, they will not have to work here at all. You guys, let me tell you that without working here, you cannot earn money anywhere. Friends, let me tell you that

multi level marketing is a business that is exactly like a mountain. If you want to dig it with a spoon, you will not be able to dig it all, nor will you be able to get it yourself with the help of ax. You will need JCB to find it. Similarly, in multi-level marketing too, you should get lots of tips and tricks, with the help of which you can dig the mountain or multi-level marketing.

If you work properly in multi-level marketing and keep developing your skills, then you will be able to earn a lot of money from here, but if you keep thinking in multi-level marketing, nothing has been done, and many more You get all the money here, you will waste your time here and you will not be able to earn anything. You have a lot of work here. Now work in the film part time, but for how long you are working, you will have to work with your mind. In multi level marketing, there are some steps which are very important. You have to follow them everyday so that you can go far ahead in multi level marketing. In this post, I will tell you about the steps by doing them completely.You keep reading click here

why do we need i? Can you please explain?

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:

Hope that's clear.

Crystal.

nice algo

Great explanation! Thanks.

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 array

Cool....

Excellent Description!

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

ss

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:

why?

y ? its not working

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"

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... :)

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:

Thanks a lot!

Thnx

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())

why it is not working if we are using same array to store modified array i.e. a[i]=a[i+k)%n]

## include

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

} int main(){

}

## include

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

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

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.

i didnt get u

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

an inner loop will not cause his program to time out. I don't believe the variable n was ever initialized, so the loop is approaching a value of n that isn't defined.

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.

My implementation of this in java didn't have this error.

use only int

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.

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

Brilliant explanation!

good explanation..working fine.

nice algo...easy to understand ...thank u soo much

Adbsolute geeky, How did it appeared to your mind ?

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

howdid youknow to use modulousand how did you come up thinking that logic ?thanks in advance.

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

This is super helpful, thanks so much for sharing!

cool

really run ?

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...

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.

great explanation!

thank you. this is my aha moment. :)

Superb explanation, now I jnow why Data Structures are imp.

Your approach shows how things should be done. I ll be soon implementing this on Python and post the same, dats gonna help many developers

Nice explanation. helped me a lot. Thanks You

Awesome Explanation....Tq

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?

Great explanation!Thanks

great way of explaining.big thank!

Nice algo..

Good Solution.

simple is peace

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

but im getting timed out if i do like this for 2 test cases

Greatest explanation so far. Thanks!

Well Explained !!

Can you please also tell me the logic of right rotation .

Here is the answer for right rotation:

can you explain this please

This is my code and it passes all the test cases.

## include

using namespace std;

int main() { int n,d; int a[n]; for(int m=0;m>a[m]; } cin>>d; for(int i=1;i<=d;i++) { int k=0; for(int j=1;j

return 0; }

Thanks for the explanation

great explaination..

The only solution that explained it fully. Very clear.

Amazing you are a nice explainer . I impressed.

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.

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;

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]; }

nice algorithm manish

This answer is true for right shifting, for left shifting test cases are failing.

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

According to given constraint : 1 <= d <=n, d will not exceed n

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

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.

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

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

Correct!

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.

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;

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.

(i + shift) % lenght Should be enough

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.

modular arithmetic is cool. I solved that way too

Can you please explain how that works?

Hello, where did this solution from? what should I study to be able to come up with solutions like this?

I love your writing, so neat!

Good solution

Looks a lot like my C# solution:

Perfect solution. Thanks for sharing

Nice solution. You dont need:

This line usefull when n >= a.Length

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.

Nice

Could you please explain your solution..?

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.

`what about this?

static int[] rotLeft(int[] a, int d) {

Awesome!

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

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

I agree

Oh my goodness! You are the best!

Agreed

what if newLocation becomes negative

then you send it to the end of the array

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.

What if lengthOfArray < shiftAmount? I think you should use abs value

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

You deal with lengthOfArray < shiftAmount by using:

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.

Aweosme !!!

pretty simple in js:

even simpler is a.splice(k).concat(a).join(' ')

what does a represent?

The array of initial values.

Did something similar in C#..

Or you can one line it with LINQ

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

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?

O(n)

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.

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

mine is also a brute force approach but it worked check it out if it helps you

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

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).

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

i got time out for tc#8 in c why??????

Iterate over array only once

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

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]

My Solution :

with one for loop i have subitted the code

Can I ask how you managed that?

Nice one! Didn't even think of that

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

Yes, no inbuilt functions can be used. They ask that in interviews.

pretty elegant solution

indeed, forgot that

`end`

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

nice one

i think that the new location = ((i + Shift)) % lenght of array

godlike solution.

this doesnt work if you shift by 3.

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

wouldn't then space complexity be O(n)

Very nice.

@hitscotty what brought you to modular arithmetic for this solution?

what if shiftAmount is greater than length of array

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..

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.

rishabh10 can u please explain ??

It is not following the instructions. Sorry.

Great Logic!! Thank you so much!!

can u pls expalin what is shiftAmount???

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

right rotation : b[i] = a[(i-k)%n]

Right rotation can be done by changing the '-' sign.. Use [(n+k+i)%n] one in scan function.. and also it is useful to keep in mind ,1 right roation=(n-1)left rotation..

Hey, guys

Here is a solution based on modular arithmetic for the case when k > n:

(note:

n - abs(k-n)can be collapsed to a single number)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.

I understand how this works, but how did you think of it?

Worked like a charm! Thanks!

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(); }

Superb man.....

That's nice but its kinda cheating :)

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.

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

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

very good, thanks!!!

can u please elaborate some more about your code as i dont have much knowledge about modular maths

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 :)

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.

what is in.nextInt() here.

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.

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

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.

Brilliant

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

Very celever! thanks.

reverse it

arr1=a[0:d]

arr2=a[d:]

return arr2+arr1

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

nice code tq

Welcome.

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)

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.

vera level..!

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?

helps a lot

Verry Good!

I saw this answer in stackoverflow too.. Please be kind enough to explain this.

Thanks

Tried a different approach

But isn't the whole point that you are not placing them as they come, the array is pre-populated and

thenrotate it. My solution is O(dn), not sure if there is anything better. Clearly I am not an algorithm guy (anymore)!Excellent !!! I am new to problem solving. I had solved it via normal shifting using one for loop and one while loop. How did you arrive at this kind of solution?? Little bit of explanation as what you thought while solving this would help a lot.

Thanks.

I don't see my submission in the discussion board. Are you reviewing my solutions?

How can I do this in C++?

a[newLocation] = in.nextInt();

If the number of rotations are greater than array length (I know it's less than array length which is given in the question, let us assume), then how would this formula change? BTW That's a great way to get the array indices without having to traverse the whole array

Neat Solution. A nice add would be shiftAmount = shiftAmount % lengthofArray; in the cases where shiftAmount exceeds the array length.

Interesting take on the problem!

I'm just mentionning this for completeness' sake but not actually solving the problem as asked, which is to write a separate function :)

Also, a follow-up question might be "improve your function so that it rotates the array in-place"

Nice solution! Thanks for sharing :)

How do you people come up with such optimization? my mind doesn't seem to work :(

I was thinking to do the same but thought not gonna do this with arithmetic so I just looped twice.

sorry to bother..i'm having trouble calculating for these values.. array length=5, no._of rotations=7.

if i take i=0 i=(0+(5-7)%5); which is equal to -2??

what am i doing wrong?

Great solution! It's possible to simplify that by finding new position as: