Rotating an array to the left without using shift

Question

I was able to get my array to sort to the right but, struggling to get the left rotation to work for example [1, 2, 3, 4, 5, 6, 7, 8] if rotated to the left 4 spaces [4, 5, 6, 7, 8, 1, 2, 3] I feel like it's super simple and just a small change to my current right rotation but, I'm stumped.

if (direction == "right")
            {
                {
                    //make spaces<nums.Length
                    if (spaces > newArray.Length)
                    {
                        while (spaces - newArray.Length >= 0)
                        {
                            spaces = spaces - newArray.Length;
                        }
                    }

                    if (spaces == 0)
                    {

                    }
                    else
                    {
                        int[] temp = new int[spaces];

                        //move to a temp array
                        for (var i = temp.Length - 1; i >= 0; i--)
                        {
                            temp[i] = newArray[newArray.Length - spaces + i];
                        }
                        //push to the end
                  for (var j = newArray.Length - spaces - 1; j >= 0; j-   -)
                        {
                            newArray[j + spaces] = newArray[j];
                        }
                        //put the ones in temp array back to the top
                        for (var s = 0; s < temp.Length; s++)
                        {
                            newArray[s] = temp[s];
                        }
                    }
                }
            }

As long as you are allocating a utility array anyway, I think it's a lot simpler to just build the new sequence there and replace the original array with the new one. — 500 - Internal Server Error, Aug 07 '19 at 15:00
Possible duplicate of [How to efficiently rotate an array?](https://stackoverflow.com/questions/38482696/how-to-efficiently-rotate-an-array) — Owen Pauling, Aug 07 '19 at 15:00
https://codereview.stackexchange.com/questions/214680/hacker-rank-array-left-rotation — Owen Pauling, Aug 07 '19 at 15:02

Dmitry Bychenko · Accepted Answer · 2019-08-08T07:17:03.613

5

Wel, if you want it simple, try Linq and modulo arithmetics:

  int[] array = new int[] { 1, 2, 3, 4, 5, 6, 7, 8 };

  int shift = 4;

  int[] result = Enumerable
    .Range(0, array.Length)
    .Select(i => array[(i + shift % array.Length + array.Length) % array.Length])
    .ToArray();

Same modulo arithmetics and no Linq

  int shift = 4;

  int[] result = new int[array.Length];

  for (int i = 0; i < result.Length; ++i)  
    result[i] = array[(i + shift % array.Length + array.Length) % array.Length];

If you want to rotate to right, assign negative values to shift.

Edit: what's going under the hood, modulo arithmetics explained. Our task is when we are given i (index of result) to compute index of the initial array:

 array  = {1 2 3 4 5 6 7 8}
 result = {5 6 7 8 1 2 3 4}

as we can see,

 index = i + shift

when shift is small enough (5 is taken from 0 + 4 == 4th index). However we can't exceed arrays length but should subtract it (i.e. restart from 0)

 7 + 4 == 11 -> 11 - 8 == 3

I.e.

 index = i + shift

 index >= array.Length 
   ? index - array.Length // index is too large, restart from 0
   : index;               // index is small enough

This operation is equal to remainder %:

 index = (i + shift) % array.Length

It's good enough, but we still have 2 specific issues with .Net:

i + shift can result in integer oveflow (when, say shift = int.MaxValue)
.Net can well return negative remainder (if shift < 0)

That's why shift % array.Length to meet the first issue and + array.Length for the second. Finally

(i + shift % array.Length + array.Length) % array.Length

edited Aug 08 '19 at 07:17

answered Aug 07 '19 at 14:59

Dmitry Bychenko

180,369
20
160
215

Too bad I can't upvote twice for the *non-linq* version. However, if you can explain how the modulo arithmetics work, for this case, this answer will be perfect – Cid Aug 07 '19 at 15:03
Well the issue here is I'm not allowed to do it the easy way that's why its so drawn out. – Zdad91 Aug 07 '19 at 15:07
I cant use the shift op unfortunately – Zdad91 Aug 07 '19 at 15:09
3

@Zdad91 There's no shift op used. It's just a variable name. – itsme86 Aug 07 '19 at 15:10
2

You wouldn't want to use the shift op anyway. It makes no sense in this context. It's for shifting bits, not array elements. – itsme86 Aug 07 '19 at 15:14
@Zdad91 if this answers your question, you can tick the check mark, below the score of this answer (top left of that answer). This is rewarding for you and the one who answers your question (both earn reputation) and this will tells the future readers that they can use this answer if they have the same question than you – Cid Aug 08 '19 at 07:15

Rotating an array to the left without using shift

1 Answers1