3
\$\begingroup\$

I took a stab at solving this problem from Hackerrank in Javascript, and would like your valuable feedback as to time/space complexity and just about any additional improvements.

Problem URL: https://www.hackerrank.com/challenges/cut-the-sticks

My JS implementation:

function main() {   
    var n = parseInt(readLine());
    arr = readLine().split(' ');
    arr = arr.map(Number);
    
    arr = arr.sort(function(a,b){ return a-b; });
    
    function cut(barr){
        if(barr.length>0){//checks array length
            var min = barr[0]; //save min value in current array
            process.stdout.write(barr.length+'\n'); //write initial array length
            var b = [];
            for(var i=0; i<barr.length; i++){ //iterate over array
                var result = barr[i]-min; //math ops
                if(result>0){
                    b.push(result); //build new array if value is greater than 0
                }
            }
            
            cut(b); // call cut operation again with new array
        }else{
            return; //halt operation if no values left to check for
        }
    }
    
    cut(arr);
    
}

\$\endgroup\$
5
\$\begingroup\$

Once the array is sorted, as you have it, the crux of this algorithm is simply:

subtract the smallest element from every element, then remove elements that equal 0

With es6 and method chaining, this can be expressed in a single line of code. The rest is just the boilerplate and a condition to check when the recursion is finished -- all similar to what you have now.

Here's the rewrite:

function main() {
  readLine();
  const input = readLine().split(' ').map(Number).sort((a,b) => a-b );
  cut(input);

  function cut(arr) {
    if (!arr.length) return;
    console.log(arr.length);
    cut(arr.map(x => x - arr[0]).filter(x => x > 0)); // <-- the essence of the algorithm
  }
}

I should also point out that the above, as well as your solution, runs in \$O(n^2)\$. You can in fact do better: \$O(n\log n)\$. Because after the array is sorted, you can solve the problem with a single pass through the array, as follows:

function main() {
  readLine();
  const input = readLine().split(' ').map(Number).sort((a,b) => a-b );
  cut(input, input[0]);

  function cut(arr, min) {
    if (!arr.length) return;
    console.log(arr.length);
    while(arr[0] == min) arr.shift();
    cut(arr, arr[0]);
  }
}

Here we're taking advantage of the fact that after each cut, the elements that are removed are precisely those equal to the minimum element. And to produce the output required for the problem, we notice that we don't actually have to do the cuts for every element of the list. We merely have to remove the elements of 0 length.

\$\endgroup\$
  • \$\begingroup\$ Nice answer. In the second solution, what about not removing elements at all? After all, all you need is the count of the same minimum values. \$\endgroup\$ – janos Oct 16 '16 at 6:39
  • \$\begingroup\$ yeah, i like it. \$\endgroup\$ – Jonah Oct 16 '16 at 6:42
  • \$\begingroup\$ Thanks @jonah! totally digging the ES6 improvements. Question on the 2nd solution though: The problem states to record length of the array everytime array values are subtracted by its minimum value. It seems that this solution is removing 1st element from ascending values in array. So if there were [1, 1, 2, 3, 4], it record the length of the array twice on the first two iteration. Any thoughts? \$\endgroup\$ – Still Questioning Oct 17 '16 at 19:34
  • \$\begingroup\$ Thanks @StillQuestioning. Actually, it will remove both 1s. The while ensures that. It's saying "chop of the first element as long as the first element is equal to the min". \$\endgroup\$ – Jonah Oct 17 '16 at 19:38

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.