1
\$\begingroup\$

I was recently doing a challenge on Codewars and this is what challenge said:

There are no explanations. You have to create the code that gives the following results:

oneTwoThree(0)['0', '0']
oneTwoThree(1)['1', '1']
oneTwoThree(3)['3', '111']
oneTwoThree(19)['991', '1111111111111111111']


I have solved the challenge but it appears to be quite slow and I was hoping to get some constructive ideas on how to improve the speed and efficacy of this code thanks.

function oneTwoThree(n) {
  var finalOutput = ['', ''],
    slotsArray = [],
    sum = 0,
    currentSlot = 0,
    slots = 1;

  /*
      My Idea was to create an array and the sum of that array will be equal to the parameter given "n". The array will have slots and the number of slots is unknown because the parameter "n" is arbitrary. each slot will contain a number from 9-1, we will start out with 9 because it is the highest, I will add all the slots and the sum must be equal to parameter "n" thus will give us the first item in our final array.
  */
  if (n >= 10) {
    while (!(9 * slots >= n)) { // check how many slots are needed
      slots += 1;
    }
    while (slotsArray.length != slots) {
      // place a 9 in every slot, starting with the highest numbern this should give us something like "[9,9,9]" for examply
      slotsArray.push(9);
    }

    // this is how I will keep track of what slot I am currently in and we will start from right to left.
    currentSlot = slotsArray.length - 1;

    for (var i = 0; i < slotsArray.length; i++) {
      //here I test if the sum of the array is equal to "n"
      sum += slotsArray[i];
    }

    // if it is not equal we proceed here.
    while (sum != n) {
      slotsArray[currentSlot] -= 1; // subtract 1 from the current slot example: [9,9,8]

      // I check agian if the sum is equal to n
      for (var i = 0; i < slotsArray.length; i++) {
        sum += slotsArray[i];
      }

      // reset the sum to 0 if its not equal
      if (sum != n) {
        sum = 0
      }

      // This will continue until if finds the sum that equals "n"
    }

    // convert the array into a string for the final output
    for (var i = 0; i < slotsArray.length; i++) {
      finalOutput[0] += String(slotsArray[i]);
    }

    while (finalOutput[1].length != n) {
      finalOutput[1] += '1';
    }
  }

  // if the parameter "n" is less than 10 
  if (n < 10) {
    finalOutput[0] = String(n);
    if (n == 0) {
      finalOutput[1] += String(n);
    } else {
      while (finalOutput[1].length != n) {
        finalOutput[1] += '1';
      }
    }
  }
  console.log(finalOutput);
  return finalOutput;
}
oneTwoThree(19);
oneTwoThree(1);
oneTwoThree(7);
oneTwoThree(36);
oneTwoThree(0);

\$\endgroup\$
1
\$\begingroup\$

Do you need to iterate?

There is a lot of room for improvement..

Use one loop if possible.

You have many loops where you iterate the same number of times. Rather than doing each loop in turn do as much as possible in one loop.

Eg.

while (!(9 * slots >= n)) { 
  slots += 1;
}
while (slotsArray.length != slots) {
  slotsArray.push(9);
}

Can be done in one

// Note new solution does not require extra item
while (!(9 * slots >= n)) { 
    slots += 1;
    slotsArray.push(9);
}

Simple conditions

Make the condition statement as simple as possible. You had !(9*slots >= n) the additional not clause is extra work (if not optimised) 9*slots < n is the same

Use variables

Some javascript engines (V8) are not as quick handling literal numbers. eg x *= 10 is slower than x *= ten but you must take into account the declaration and assignment of the variable. If you use the number once or twice there is no advantage, but if you do it many time there is.

Math rather than Loops

Alway check to see if there is a way to directly calculate the result rather than use iteration.

You do not actually need any loops

Use memory

Memory is cheap and fast, CPU cycles are not. So rather than iterate have a predefined object that can be used to create a result

You have

  while (finalOutput[1].length != n) {
    finalOutput[1] += '1';
  }

but the following is quicker (note it should be defined outside the function but in this case you may only have the function's scope)

  // long enough for all possible results?
  var ones = "111111111111111111111111111111111111111111111111111111111";
  finalOutput[1] = ones.substr(0,n);

There are many other optimisations that I have not included as the resulting optimised code is very simple and most of what you had is not needed.

Testing

To ensure I got it correct I wrote a test that compares your function to the new one. Making sure the results are the same, then running each version 100,000 times to get the performance.

There results are

// calls to function oneTwoThree Ori is the original and New is the optimised version
// time in ms (1/1000);

-- Test value : (19) -------------------
Ori : 191.53ms Mean : 0.00192
New : 22.38ms Mean : 0.00022
-- Test value : (1) -------------------
Ori : 8.78ms Mean : 0.00009
New : 6.61ms Mean : 0.00007
-- Test value : (7) -------------------
Ori : 62.03ms Mean : 0.00062
New : 6.02ms Mean : 0.00006
-- Test value : (36) -------------------
Ori : 208.12ms Mean : 0.00208
New : 18.57ms Mean : 0.00019
-- Test value : (0) -------------------
Ori : 8.47ms Mean : 0.00008
New : 4.00ms Mean : 0.00004

For the results of n < 10 the improvement is not that great but near 25%-50% is worth the effort. The improvement for n >= 10 are well worth the effort.

The new code

No loops needed. Warning longStr1s may need to be larger as I have not tested all possible inputs.

function oneTwoThree_Q(n) {
    var nine = 9; // variable = 9 is quicker than litteral value
    var slots;
    var longStr1s = "11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111";
    var longStr9s = "999999999999999999999999999999999999999999999999999999999";
    if (n < 10) {
        return ['' + n, n === 0 ? '' + n : longStr1s.substr(0,n)];
    }
    slots = Math.ceil(n / nine);
    nine += n - slots * 9;
    return [longStr9s.substr(0,slots-1) + nine, longStr1s.substr(0,n)];
}
\$\endgroup\$
  • \$\begingroup\$ Why not return ['' + n, n === 0 ? '' + n : "1".repeat(n)]; ? I think it's more readable and performance should be somewhat similar, considering that substr has been changed to be a copy, so \$O(n)\$ \$\endgroup\$ – ChatterOne Jan 12 '17 at 13:58
  • \$\begingroup\$ @ChatterOne Forgot about repeat thanks, though repeat does not have full support (IE) and I have not yet tested it on the Chrome. So far Chrome has not provided very good ES6 code with most running well under the poly fill times. But I will have a quick test and see how it compares. Will change answer to reflect results \$\endgroup\$ – Blindman67 Jan 12 '17 at 14:08
  • \$\begingroup\$ @ChatterOne Yep as i thought Chrome (and hence V8 the most likely testing platform) runs repeat nearly 5 time slower than substr. For 1000 iterations of random length str repeat got 437µs per 1000 and substr 87µs per 1000 on my win10 laptop and chrome beta Version 56.0.2924.51 beta \$\endgroup\$ – Blindman67 Jan 12 '17 at 14:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.