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
– 500 - Internal Server Error, Commented Aug 7, 2019 at 15:00

Dmitrii Bychenko · Accepted Answer · 2019-08-08 07:17:03Z

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 8, 2019 at 7:17

answered Aug 7, 2019 at 14:59

Dmitrii Bychenko

188k20 gold badges178 silver badges231 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Cid Over a year ago

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

Zdad91 Over a year ago

Well the issue here is I'm not allowed to do it the easy way that's why its so drawn out.

Zdad91 Over a year ago

I cant use the shift op unfortunately

itsme86 Over a year ago

@Zdad91 There's no shift op used. It's just a variable name.

itsme86 Over a year ago

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.

|

Rajamohan Rajendran · Accepted Answer · 2024-02-20 10:11:22Z

0

public class Solution {
    public void Rotate(int[] nums, int k) {
    int[] rotated = new int[nums.Length];

    for (int i = 0; i < nums.Length; i++) {
        int rem = (i + k) % nums.Length;
        rotated[rem] = nums[i];
    }
    Array.Copy(rotated, nums, rotated.Length);
   }

}

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

answered Feb 20, 2024 at 10:11

Rajamohan Rajendran

3691 gold badge3 silver badges13 bronze badges

Collectives™ on Stack Overflow

Rotating an array to the left without using shift

2 Answers 2

6 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related