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.
Loading...
  • Practice
  • Compete
  • Jobs
  • Leaderboard
  1. Practice
  2. Data Structures
  3. Arrays
  4. Left Rotation
  5. Discussions

Left Rotation

  • Problem
  • Submissions
  • Leaderboard
  • Discussions
  • Editorial

    You are viewing a single comment's thread. Return to all comments →

  • h276692580 3 years ago+ 5 comments

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

    0|
    ParentPermalink
    • justin_gries 3 years ago+ 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.

      2|
      ParentPermalink
    • ivan_rrr 2 years ago+ 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;
          }
      
      0|
      ParentPermalink
    • carlostse 1 year ago+ 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.

      0|
      ParentPermalink
    • nintendroid 1 year ago+ 0 comments
      [deleted]
      0|
      ParentPermalink
    • nintendroid 1 year ago+ 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;
      }
      
      3|
      ParentPermalink
      • ArshadAQ 8 months ago+ 0 comments

        Why has everyone ignored this?

        0|
        ParentPermalink
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature