0

For example the array with n=10 elements:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

gets cyclicly left-shifted by 3 so the first number is f=3 to produce the array:

[3, 4, 5, 6, 7, 8, 9, 0, 1, 2]

From i=8 to j=1 there are d=3 steps, that is the left-to-right distance d. From i=8 to j=3 there are d=5 steps, because after 2 it cyclicly jumps to 3 (think of it as a ring). How does one generally calculate the distance d between two numbers i,j, when n and f are known, assuming the array always contains cyclicly left-shifted consecutive integers initially starting from 0?

user3280015
  • 279
  • 2
  • 10
  • 1
    I don't see how the rotation by `f` affects anything here. Since you're treating the array as a ring, rotating it won't affect distances between elements. – interjay Feb 16 '15 at 15:10
  • @interjay well without the left-shifting I could simply do `d = j - i`, but this formula doesn't work after the rotation – user3280015 Feb 16 '15 at 15:11
  • Then do `(j - i) % n`. Your use of the modulo tag suggests that you knew that. `j - i` wouldn't even work before performing the rotation (e.g. going from 8 to 3 would give -5), so the rotation is meaningless. – interjay Feb 16 '15 at 15:12
  • `d = n - i + j` seems to work, or am I missing something? – IVlad Feb 16 '15 at 15:14
  • this question is worded in a very convoluted way. what does f have anything to do with anything? when you rotate an array, the separations between its elements don't change. for that matter, what does the array have anything to do with anything? if you want distance between 2 numbers mod n, then do that. – thang Feb 16 '15 at 15:15
  • @interjay oh right, i also tried `(j - i) % n` but JavaScript gave me -1 for j=3, i=4, n=10. But google calculator gave me 9 correctly – user3280015 Feb 16 '15 at 15:20
  • @IVlad even more right -_- – user3280015 Feb 16 '15 at 15:21
  • You want to find the shortest distance, correct? Not the distance in a particular direction (e.g., distance between 3 and 2 rotating around the ring in an increasing direction would be 9, in this example with 10 elements). – Aaron D Feb 16 '15 at 15:23
  • http://stackoverflow.com/questions/4467539/javascript-modulo-not-behaving and http://javascript.about.com/od/problemsolving/a/modulobug.htm. javascript is dumb. – thang Feb 16 '15 at 15:24

2 Answers2

1

If you want to know the distance in any direction, then it's just a matter of subtracting. If you have i=8 and j=5, the distance is |j-i| (absolute of j-i), so 3.

If, however, you want the amount of cycles you'd need to put j at the position of i, then it corresponds to:

if j - i < 0
    answer = j - i + n
else
    answer = j - i

So for i=8 and j=5 where n=10, it would be 5-8+10=7. But this might not even be what you want, the question isn't very clear. EDIT: wait, I was thinking from the principle that i and j were positions in the array, not values. This can be confusing :/

Domino
  • 6,314
  • 1
  • 32
  • 58
  • +1, this is what I was thinking too. Or we can write that as `(j - i + n) % n`. It will always be positive so it shouldn't matter what modulo does for negatives in whatever language. – IVlad Feb 16 '15 at 15:27
  • yes i and j are values, that's why I gave the i=8 and j=1 examples etc. – user3280015 Feb 16 '15 at 15:31
1

This problem can be reduced to the problem of finding the rotation of a string, the algorithm generally works like this:

  1. Make a copy of the original string S and then concatenate it with it. S' = SS
  2. Shift the rotated string R in S' from 0, and return the index when R is a substring of S'

For example:

S  = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
S' = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Then find

R = [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]

is a "substring" of S' when R starts at the index 3 in S':

S' = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
               ^
               | (index = 3)
              [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]

so the rotation is 3.

zs2020
  • 53,766
  • 29
  • 154
  • 219