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

Left Rotation

  • corey_t_ferguson + 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.

    • vjindal23 + 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

    • siregar_jaswir + 1 comment

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

      • corey_t_ferguson + 0 comments

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