current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 3 down vote favorite

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);
    
}

share|improve this question
up vote 4 down vote

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.

share|improve this answer
    
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. – janos♦ yesterday
    
yeah, i like it. – Jonah yesterday

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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