CODEWITHSUNDEEP
c#.netarraysalgorithm
Erez
Erez

Reputation: 6446

Rotating right an array of int in c#?

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

Upvotes: 7

Views: 7319

Answers (6)

SunsetQuest
SunsetQuest

Reputation: 8827

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();

Upvotes: 0

Chaholl
Chaholl

Reputation: 463

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;

Upvotes: 0

kuk_94
kuk_94

Reputation: 523

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];
    }

Upvotes: 0

chill
chill

Reputation: 16888

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;
}

Upvotes: 0

Ben
Ben

Reputation: 1963

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

Upvotes: 1

Cyril Gandon
Cyril Gandon

Reputation: 17058

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 }));
}

Upvotes: 5

Related Questions