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.
  • Practice
  • Certification
  • Compete
  • Career Fair
  • Hiring developers?
  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 →

  • corey_t_ferguson 4 years ago+ 0 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
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature