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 →

  • akueisara39 3 years ago+ 8 comments

    Each time I read an element of the array from the input, I directly assign it to the array at the speific index after shifting. d left rotations equal (n-d) right rotations. The array has a size of n, so when the index (i+n-d) is equal to n, the index actually goes back to the starting index. I use mod to get the correct index where I want to assign the element when the index is larger than n. I'm not an english native speaker. Hope you will understand what I explain. :)

    99|
    ParentPermalink
    • ramkr7 3 years ago+ 1 comment

      thank you so much.very helpful.

      3|
      ParentPermalink
      • Tkphetla 1 year ago+ 0 comments

        This is Great

        0|
        ParentPermalink
    • motox2 3 years ago+ 1 comment

      I see a problem here. You've assumed that we can sort the array at the time of initialization itself. Though it's good, but IMHO, the real test is to sort an already existing array with space constraints.

      5|
      ParentPermalink
      • qianyaonan 3 years ago+ 12 comments

        Good thinking! I guess it could be handled with another array logically. My two cents.

            ......
            int[] getArray = new int[n];
            for (int i = 0; i < n; i++) {
                getArray[i] = scan.next();
            }
            for (int i = 0; i < n; i++) {
                array[(i + n - d) % n] = getArray [i];
            }
            for(int i = 0; i < n; i++) {
                System.out.print(array[i] + " ");
            }      
        
        8|
        ParentPermalink
        • suulisindiyaka 3 years ago+ 2 comments

          I like you code some much.PLEASE can you add some explainatioin.I will be very glad

          0|
          ParentPermalink
          • qianyaonan 3 years ago+ 1 comment

            It just generates an array first from Stdin, then illustrates the way to left-rotate an EXISTING array.

            0|
            ParentPermalink
            • vamphonephong 2 years ago+ 0 comments

              I'm failing to see where it actually does a left rotate of an existing array.

              What I'm seeing is (from assumption of ...) array[0..n] is empty initially. getArray[0..n] stores input from stdin. store rotated result into array[0..n].

              The existing array is getArray. That array is still in an unrotated order. The array[0..n] isn't considered the exiting array as it is empty.

              Challenge to you: get rid of getArray array and store input into array[] array. Rotate that array and then print the end result of that array.

              1|
              ParentPermalink
          • jeffreyzhuu 3 years ago+ 1 comment

            This code is actually quite efficient. So for the following values, n=5 (number of elements in the array), d=2 (number of rotations)and assuming i goes from 0-4. (i + n - d)%n with the iteration of i from 0-4: (0+5-2)%5=3 (1+5-2)%5=4 . . . (4+5-2)%5=2 So essentially, you are changing the locations of the elements in the array. How the "%" works is that it takes the remainder. So for example, 1%7=1 since 1 cannot be divided by 7 which means 1 is the remainder.

            3|
            ParentPermalink
            • ravilog91 3 months ago+ 0 comments

              that's great, can you provide any mathematical illustration to arrive (i+n-d)%n ?

              0|
              ParentPermalink
        • nunziomeli5 3 years ago+ 2 comments

          That's not the aim of the exercise... You have to fill the array and after shift!!! In this way is easy and you are not resolving the left shift problem.

          -12|
          ParentPermalink
          • akueisara39 3 years ago+ 5 comments

            For me, it's just an alternative way. There's not only one way to think for the same problem whatever the solution is good or bad. I shared my solution because I hadn't seen anyone think the same way and I thought it was good to learn from people's comments on my solution.

            56|
            ParentPermalink
            • shankar455161 2 years ago+ 0 comments

              A good solution by you!

              0|
              ParentPermalink
            • ekimalc 2 years ago+ 0 comments

              I like your solution, elegant and efficient. It took my two days for mine and even now has timeout issues when testing. I have good envy now. Well done!

              3|
              ParentPermalink
            • govind_yadav_141 2 years ago+ 1 comment

              I really like your solution as you have reduce the time complexity to O(n^2) while is very efficeint compare to my program which has a T(n) = O(n^3)

              0|
              ParentPermalink
              • Sufiyan 11 months ago+ 0 comments

                How the complexity is quadratic? It is O(n), right?

                5|
                ParentPermalink
            • skandy 1 year ago+ 1 comment

              This solution will not work when rotation is greater than array size, meaning d > n. Java returns negative result if you perform % operation on a negative number. And that negative number will throw an

              java.lang.ArrayIndexOutOfBoundsException
              

              Eg. n = 4, d = 7

              Starting with i=0, a[(i+n-d)%n] will give a[(0 + 4 - 7)%4] => a[(0 + (-3))%4] => a[(-3)%4] => a[-3]

              Range of a is from 0 to n. Hence the error

              3|
              ParentPermalink
              • ravievolution87 1 year ago+ 0 comments

                for this case you can check for d>n and d = d%n then d will be in range of 0 to n and the above solution will work perfectly :)

                2|
                ParentPermalink
            • ravilog91 3 months ago+ 0 comments

              this is the simplest and most efficient solution. I was struggling Time out error with mine.

              0|
              ParentPermalink
          • [deleted] 2 years ago+ 2 comments

            It's the far superior solution. Why shift all the elements in the array individually, when you can just shift the index to achieve the same result? It's a total waste of processing to shift the entire array. What if the array was 1,000,000,000 elements long, and you had to shift multiple times? In an interview they would probably expect you to do it this way, with an explanation of your logic.

            14|
            ParentPermalink
            • Wafflenaut 2 years ago+ 0 comments

              I agree. If they wanted something to shift elements of an array, they should have asked for a function to do so.

              1|
              ParentPermalink
            • eniv230862 2 years ago+ 0 comments

              In my case, they were expecting the function that returns a vector with all the elements rotated any number of times. So, the best way is to take the number of shiftings and move the index that number of times, and do the shift only one time.

              1|
              ParentPermalink
        • tanp1 2 years ago+ 0 comments

          Have you tried running this? You actually run into an issue where you just propagate the first value in the array across all other indices in the array using your method.

          The second for loop moves the value at index 0, the 1, over to index 1, overwriting the value 2 at index 1, and then this 1 gets written into all the other indices as a result.

          0|
          ParentPermalink
        • tp2124 2 years ago+ 3 comments

          Solid answer. I would like to point out to people that this does require double the memory of the intial answer as this requires a second array to store all the properly ordered array. If you're on a memory tight situation, this would not be a favorable solution.

          0|
          ParentPermalink
          • corey_t_ferguson 2 years ago+ 2 comments

            To solve this, I've shifted the elements in the array in O(n) time and O(n) memory (vs O(2n)). Not as easy on the eyes, though :(

            function processData(input) {
              // get `n` and `d` from input
              const lines = input.split('\n');
              const firstLine = lines[0].split(' ').map(Number);
              const n = firstLine[0];
              const d = firstLine[1];
            
              // process each line
              lines.slice(1, lines.length).forEach(line => {
                // no need to shift in these cases
                if (n === 1 || d === n) {
                  console.info(line);
                } else {
                  // shift digits
                  const a = line.split(' ').map(Number);
                  let lastLastItem = null;
                  let count = 0;
                  let i = 0;
                  while (count < n) {
                    i++;
                    const start = i;
                    let j = start;
                    do {
                      count++;
                      let lastItem = lastLastItem;
                      lastLastItem = a[j];
                      a[j] = lastItem;
                      j = shiftLeft(n, d, j);
                    } while (j !== start);
                    a[start] = lastLastItem;
                  }
                  console.info(a.reduce((acc, value) => {
                    return acc+' '+value;
                  }));
                }
              });
            }
            
            /**
             * @param {Number} n total number of elements
             * @param {Number} d number of shifts to left
             * @param {Number} i index to begin shifting from
             * @returns {Number} new index after shifting to left
             */
            function shiftLeft(n, d, i) {
              return (n-d+i)%n;
            }
            

            I'm ignoring the processing time on input string manipulation and such. This examples assumes they gave us an existing array to manipulate.

            0|
            ParentPermalink
            • vjindal23 2 years ago+ 0 comments

              Hey! Could you include comments in your code please? I use C and dont kow other language as of now but would like to learn from your solution O(n) is preety nice

              0|
              ParentPermalink
            • siregar_jaswir 2 years ago+ 1 comment

              i think your solutions is O(n^2) for the worst case.

              2|
              ParentPermalink
              • corey_t_ferguson 9 months ago+ 0 comments

                It looks like it, because of the nested loops. But it'll break out of all loops after n loops.

                0|
                ParentPermalink
          • corey_t_ferguson 9 months ago+ 0 comments

            Revisited this with an easier-on-the-eyes solution that finishes in O(n) time with O(n) memory.

            function main() {
              	// ...
                loopUntilAllSwapped(a, d);
                console.log(a.join(' ') + '\n');
            }
            
            /**
             * If a.length can be divided by d evenly, swapSeries will end 
             * where it started without swapping all numbers.
             * This function ensures that all numbers are swapped.
             * 
             * Variables:
             * a: array of numbers
             * d: number of left-rotations to perform
             * c: count of numbers swapped
             * i: index to start swapSeries() from
             */
            function loopUntilAllSwapped(a, d) {
                let c = 0;
                let i = 0;
                while (c < a.length) {
                    c += swapSeries(a, i, d);
                    i++;
                }
            }
            
            /**
             * Swaps elements in an array in-place.
             *
             * Variables:
             * a: array of numbers
             * i: index to start with
             * d: number of left-rotations to perform
             * c: count of numbers swapped, returned to loopUntilAllSwapped()
             * iS: index source (index of number to be moved)
             * iD: index destination (index iS will be moved to)
             * q: a queue that acts as a temporary buffer for numbers as they 
             *     move from source to destination
             *
             * Algorithm:
             * 1. Find index destination (iD) of a[iS] after d rotations to 
             *    left
             * 2. Place destination in temporary buffer (q).
             * 3. Replace destination with index source (iS) value (a[iS]).
             * 4. Repeat until we end where we started (iS === i) 
             */
            function swapSeries(a, i, d) {
                let c=0;
                let iS = i;
                let q = [a[iS]];
                do {
                    let iD = h(a.length, d, iS);
                    q.push(a[iD]);
                    a[iD] = q.shift();
                    iS = iD;
                    c++;
                } while (iS !== i);
                return c;
            }
            
            /**
             * A constant-time formula to find index destination of i 
             * after d rotations to left.
             */
            function h(n, d, i) {
                return ((n-d%n)%n+i)%n;
            }
            
            0|
            ParentPermalink
          • CS234_SHREY 3 months ago+ 0 comments

            YOU don't need second vector for this. Just store the 0th index of a vector in some temp variable and when the whole array gets shifted by one left rotation ,store it at the n-1th index. Repeat the process till d becomes zero.

            0|
            ParentPermalink
        • iam_ghanshyam 2 years ago+ 0 comments

          In my opinion, the 3rd for-loop is unnecessary.. Instead it should be merged with the 2nd one.

          0|
          ParentPermalink
        • alxsm 2 years ago+ 0 comments
          [deleted]
          0|
          ParentPermalink
        • liuch_sdu 2 years ago+ 0 comments

          This should be called circle array,haha

          0|
          ParentPermalink
        • tomisin 2 years ago+ 0 comments

          Doesn't this use extra space?

          0|
          ParentPermalink
        • wyrlvillazorda 2 years ago+ 1 comment

          for me is: (d + i) % n

          1|
          ParentPermalink
          • 15euec173 1 year ago+ 1 comment

            what does it mean...????

            0|
            ParentPermalink
            • 15euec173 1 year ago+ 0 comments

              %.....?

              -1|
              ParentPermalink
        • ajinkya_ghonge 2 years ago+ 0 comments

          One drawback i can see here is that you are actually holding the IO operation while your code is getting executed. This will not affect for an input of 100, but think about an input of millions

          0|
          ParentPermalink
        • karhik110 1 year ago+ 0 comments

          nice!! different way of thinking! you cahnged the way of thinging..

          0|
          ParentPermalink
        • pmahanth967 1 year ago+ 0 comments

          getArray[i] = scan.next(); this is an error.It cannot be converted into string.

          getArray[i] = scan.nextInt(); this is correct statement.

          0|
          ParentPermalink
    • justin_gries 3 years ago+ 0 comments

      Very nice. I didn't even think to assign the integers to their "new" positions in the array as they are read in.

      0|
      ParentPermalink
    • anandki 2 years ago+ 0 comments

      Concise code and Wonderful explanation.This should go to Editorial.

      2|
      ParentPermalink
    • Purushotam_ 2 years ago+ 0 comments

      why can't we do the left rotation. like you said d left rotation is equal to n-d right rotation.what is problem in that...

      0|
      ParentPermalink
    • Infinity_Coder 2 years ago+ 0 comments

      Given an array of n integers and a number, d, perform d left rotations on the array. So this means that the array is already given. Then we have to perform left rotation on that. Your solution may produce the required results, but as others have pointed out, I think that is not what has been asked in the solution. We have been given a complete array, and on that we have to perform the rotation.

      0|
      ParentPermalink
    • nelpontejos 5 months ago+ 0 comments

      thanks

      0|
      ParentPermalink
    • sriram_pant5 5 days ago+ 0 comments

      very convenient solution

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