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.
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!
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;
Arrays: Left Rotation
You are viewing a single comment's thread. Return to all comments →
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
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.
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 how did you know to use modulous and 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:
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