You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
40 lines
734 B
Ruby
40 lines
734 B
Ruby
#Juggling Algorithm for array rotation!
|
|
#Time complexity: O(n) , Auxiliary-Space: O(1)
|
|
|
|
|
|
def left_rotate_array(a, d) #Input array "a" and rotation by "d" elemets
|
|
n=a.length
|
|
if n>0
|
|
if d>n # if d>n ,we take modulo n
|
|
d%=n
|
|
end
|
|
|
|
for i in 0...gcd(d,n)
|
|
temp=a[i]
|
|
j=i
|
|
while(true)
|
|
k=j+d
|
|
if k>=n
|
|
k=k-n
|
|
end
|
|
if k==i
|
|
break
|
|
end
|
|
a[j]=a[k]
|
|
j=k
|
|
end
|
|
a[j]=temp
|
|
end
|
|
|
|
end
|
|
return a
|
|
end
|
|
|
|
|
|
def gcd(x,y)
|
|
if y==0
|
|
return x
|
|
else
|
|
return gcd(y,x%y)
|
|
end
|
|
end |