Rotating right an array of int in c#?

Question

I've got an homework assignment:

need to implement a function (RotateRight) that gets an array of INT and a number:

int[] res = RotateRight(new int[] { 1, 2, 3, 4, 5, 6 }, 2);
//so then res will be {5,6,1,2,3,4}

and return the array after rotating all of the items to the right according to the number that been given, In our case 2.

And I have to do this efficiently in terms of memory space.

my best idea is:

if the number that been given is x, to use a new int[] tmpArray in the size of x to copy all the last x items to it. then with a for loop to shift all the rest of the int to the right. And in the end to copy the items in the tmpArray to the begining of the original array.

Thanks in advance for any advice or help

If you passed 6 would you get back the original array? Is passing 7 the same as passing 1? — Kevin DiTraglia
– Kevin DiTraglia, Commented Nov 12, 2013 at 16:12
Andrew Walters - thanks for the comment, i've fixed my question Kevin DiTraglia - yes — Erez
– Erez, Commented Nov 12, 2013 at 16:20
Using a copy of the array is hardly "efficiently in terms of memory space". This can be done in-place. — chill
– chill, Commented Nov 12, 2013 at 16:42

Cyril Gandon · Accepted Answer · 2013-11-12 16:05:04Z

5

You can use the beauty of the Linq langage to return an IEnumerable without dealing with array size:

/// <summary>
/// Get c = a mod (b) with c in [0, b[ like the mathematical definition
/// </summary>
public static int MathMod(int a, int b)
{
    int c = ((a % b) + b) % b;
    return c;
}
public static IEnumerable<T> ShiftRight<T>(IList<T> values, int shift)
{
    for (int index = 0; index < values.Count; index++)
    {
        yield return values[MathMod(index - shift, values.Count)];
    }
}

Usage :

[TestMethod]
public void TestMethod1()
{
    var res = ShiftRight(new [] { 1, 2, 3, 4, 5, 6 }, 2).ToArray();
    Assert.IsTrue(res.SequenceEqual(new[] { 5, 6, 1, 2, 3, 4 }));
}

answered Nov 12, 2013 at 16:05

Cyril Gandon

17.1k15 gold badges84 silver badges124 bronze badges

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

3 Comments

Erez Over a year ago

Thanks! looks elegant

Servy Over a year ago

Note that for a right shift you can just use %. You only need modulus for a left shift.

Ben Over a year ago

Looks nice and in the real world probably the best answer but creates a brand new array so not efficient as it could be. If you want to do this in place (no need to create a new array) see my answer below

Ben · Accepted Answer · 2013-11-12 17:11:17Z

1

Most memory possible makes no sense, you probably mean as little memory as possible? If so you should swap each item in the array using XOR, i.e:

var a = 2096;
var b = 842390;

a ^= b;
b ^= a;
a ^= b;

would swap these numbers.

EDIT

Code to do the whole thing in place:

    public static void RotateRight(int[] input, int right)
    {
        for (var i = 0; i < right; i += 1)
        {
            RotateRightOne(input);
        }
    }

    public static void RotateRightOne(int[] input)
    {
        var last = input.Length - 1;
        for (var i = 0; i < last; i += 1)
        {
            input[i] ^= input[last];
            input[last] ^= input[i];
            input[i] ^= input[last];
        }
    }

Usage:

    var arr = new[] {1, 2, 3, 4, 5, 6};
    RotateRight(arr, 2);

As Servy points out, this is only for integers

edited Nov 12, 2013 at 17:11

answered Nov 12, 2013 at 16:08

Ben

1,96316 silver badges17 bronze badges

4 Comments

Rawling Over a year ago

That's a neat trick, but can you figure out which pairwise switches to perform in order the cyclical shift?

Servy Over a year ago

Also note this option only works for integer arrays; it can't handle any other kind of array.

Cyril Gandon Over a year ago

This is particulary slow for big shift. In fact, for a random shift, this is a O(n^2)

Ben Over a year ago

@Cyril: I'm aware of that, this is just homework with the requirement to use the least amount of memory possible... No one said anything about speed

chill · Accepted Answer · 2013-11-13 23:43:26Z

Don't know C#, but here are two C++ versions, both in place, the first (rotate) does the minimum possible number of element moves by exploiting the cyclic structure of the rotation permutation, the second (rotate_k) just does 2*n moves for an array of length n. In both versions it's used that rotate right by k is the same as rotate left by n - k % n, so they in fact do the equivalent left rotation.

#include <iostream>
#include <vector>
#include <algorithm>

void
rotate (size_t k, std::vector<int> &a) {
    size_t n = a.size();
    k = n - k % n;

    size_t m = n;

    size_t i = 0;
    while (m > 0) {
        int t = a[i];
        size_t j = i;
        while (i != (j + k) % n) {
            a[j] = a[(j + k) % n];
            j = (j + k) % n;
            --m;
        }
        a[j] = t;
        --m;
        ++i;
    }
}

void
rotate_k (size_t k, std::vector<int> &a) {
    size_t n = a.size();

    k = n - k % n;

    std::reverse (a.begin(), a.end());
    std::reverse (a.begin(), a.begin() + n - k);
    std::reverse (a.begin() + n - k, a.end());
}

int
main () {
    std::vector<int> a = { 1, 2, 3, 4, 5, 6, 7, 8, 9};
    rotate (12, a);

    for (auto i : a)
        std::cout << i << " ";

    std::cout << std::endl;
}

kuk_94 · Accepted Answer · 2017-01-27 19:09:58Z

0

You just need to figure out the final index for each element after rotating it k times rather than actually rotating it k times. This worked for me:

for(int i=0;i<a.Length;i++){
        rotated[(k+i)%(a.Length)]=a[i];
    }

answered Jan 27, 2017 at 19:09

kuk_94

5331 gold badge5 silver badges19 bronze badges

Comments

Chaholl · Accepted Answer · 2018-05-17 19:03:26Z

0

Here's a quick sample on rotating an array A right K steps:

    var splitPoint=A.Length-(K%A.Length);

    var result=new int[A.Length];
    int idx=0;
    for(var pos=0;pos<A.Length;pos++)
    {
      if(pos<A.Length-splitPoint)
      {
        result[pos]=A[splitPoint+pos];    
      }
      else
      {
        result[pos]=A[idx];
        idx++;
      }
    }

    return result;

answered May 17, 2018 at 19:03

Chaholl

4635 silver badges8 bronze badges

Comments

SunsetQuest · Accepted Answer · 2020-01-09 01:21:20Z

0

C# 8 now has Indices and Ranges

Rotate Right...

int[] r = t[1..].Concat(t[0..1]).ToArray();

Rotate Left...

int[] r = t[^1..^0].Concat(t[..^1]).ToArray();

in place of the "1" above, a variable can also be used: int[] r = t[amt..].Concat(t[0..amt]).ToArray();

answered Jan 9, 2020 at 1:21

SunsetQuest

9,0352 gold badges52 silver badges47 bronze badges

Collectives™ on Stack Overflow

Rotating right an array of int in c#?

6 Answers 6

3 Comments

4 Comments

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

3 Comments

4 Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related