We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Practice
  2. Data Structures
  3. Arrays
  4. Left Rotation
  5. Discussions

Left Rotation

  • h276692580 + 5 comments

    Did anyone consider if we cant alloc a new array to store sorted array, only operate the old array to left rotation?

    • justin_gries + 0 comments

      At the very least, you would have to allocate memory to store one integer. The question then becomes what you consider to be important: memory, or run-time, or something in between. If your primary focus is memory, then your solution is just to move EVERYTHING in the array one unit over, multiplied by the number of iterations. (You can mitigate this somewhat by right-shifting if the number of iterations is more than 1/2 the size of the array.) If your focus is time, then just transfer everything to another array, and back again, giving ~ O(2n). A decent in-between (which is what I went with) is to move only the number of elements out that you need to move (max 1/2 n) to another array, shift everything else, then re-insert the moved elements.

    • ivan_rrr + 0 comments

      It is not the best solution but it requires only one array:

      static void Main(String[] args) {
        string[] read = Console.ReadLine().Split(' ');
        int n = int.Parse(read[0]);
        int d = int.Parse(read[1]);
        int[] array = new int[n];
        array = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse);
        
        for(int q=0;q<d;q++)
            for(int i=0;i<n-1;i++)
            {
                swap(array, i,i+1);
            }
        
        for(int y=0;y<n;y++)
            Console.Write(array[y] + " ");
        Console.WriteLine();
    }
    
    static void swap(int[] input, int indexA, int indexB)
    {
        int tmpA = input[indexA];
        int tmpB = input[indexB];
        input[indexA] = tmpB;
        input[indexB] = tmpA;
    }
    • carlostse + 0 comments

      Yes. But I think it will slower than 

      int *swp = new int[n];
memcpy(swp, (const void *)(arr + d), (n - d) * sizeof(int));
memcpy(swp + (n - d), (const void *)arr, d * sizeof(int));

      Correct me if I am wrong.

    • nintendroid + 0 comments
      [deleted]
    • nintendroid + 1 comment

      My in-place O(n) solution. No allocation required

      template <typename Iterator>
static void rotate_left(Iterator begin, Iterator mid, Iterator end) {
    while (begin != mid && mid != end) {
        auto it = mid;

        while (begin != mid && it != end) {
            std::swap(*begin++, *it++);
        }

        if (begin == mid) {
            mid = it;
        }
    }
}

int main() {
    int n{};
    int k{};
    std::cin >> n >> k;

    std::vector<int> values(n);
    std::copy_n(std::istream_iterator<int>(std::cin), n, values.begin());

    auto mid = values.begin();
    std::advance(mid, k);
    ::rotate_left(values.begin(), mid, values.end());
    std::copy(values.begin(), values.end(), std::ostream_iterator<int>(std::cout, " "));
    
    return 0;
}
      • ArshadAQ + 0 comments

        Why has everyone ignored this?