2
\$\begingroup\$

I want to achieve this:

  • digPow(89, 1) should return 1 since \$8^1 + 9^2 = 89 = 89 * 1\$
  • digPow(92, 1) should return -1 since there is no \$k\$ such that \$9^1 + 2^2\$ equals \$92 * k\$
  • digPow(695, 2) should return 2 since \$6^2 + 9^3 + 5^4 = 1390 = 695 * 2\$
  • digPow(46288, 3) should return 51 since \$4^3 + 6^4 + 2^5 + 8^6 + 8^7 = 2360688 = 46288 * 51\$

I have implemented it like this:

function digPow(n, p){
  var digits = n.toString().split('');
  var result = 0;
  for(var i=0; i<digits.length; i++){
    result = result + Math.pow(digits[i], p);
    p++;
  }
  var data = result/n;
  if(result % n === 0){
  return data;
  }else{
  return -1;
  }
}
\$\endgroup\$
2
\$\begingroup\$

Some benchmarks

I am guessing a function like this is written, apart from an exercise, to search for power numbers. Thus execution time is important.

String manipulation and type conversion is not something that javascript likes to do, so running the two given answers in a profiler I measured the time to run the following loop.

var i;
for (i = 0; i < 1000; i += 1) {
    digPow(Math.floor(Math.random() * 10000000),i%10);
}

I ran the tests for many minutes the results were

ashraf aaref's function ran twice as fast as Oleander's on Firefox, running on an old Win10 32Bit laptop. The times; 2ms and 4ms respectively for the above loop. Which equates to 500,000 and 250,000 calls to the function digPow (plus overhead of loop and call) per sec,

The array method reduce is the bottleneck in the slowest version. For performance always avoid any of the array iteration functions as each interaction involves a function call that needs to save the current context.

Type conversion is the bottleneck in the second function.

Avoiding both bottlenecks

But there is a much faster method that avoids the type conversion

 function digPowC(n, p){
    var digits, result, i, num;
    digits = Math.floor(Math.log10(n)) + p;  // get the number of digits
                                             // add the power p
    result = 0;
    num = n;                                 // running least significant digit
    while(digits >= p){                      // Stop at p
        result += Math.pow((num % 10),digits--);  // pow least significant digit
        num = Math.floor(num / 10);
    }
    if(result % n === 0){  // vet result
        return result / n;
    }
    return -1;
} 

Which is twice as fast again at 1ms or 1,000,000 calls per second.

Which is the best, that could be debated forever as all three work except for one problem that is often forgotten when manipulating numbers.

digPow(1e100,1) is not dealt with. The two string methods fail as they try to evaluate the "e" and the pure number version fails trying to maintain the least significant digit that is way outside the 64bit Double's precision. But then we assume that arguments are vetted.

Results of a benchmark

Not runnable just hidden to avoid clutter.

// Each function is duplicated and randomly called the mean is the mean of all 4 tests
/* Raw output from tester

Test : 'Oleander'
4.155microsec 3155 samples
4.161microsec 3057 samples
4.169microsec 3128 samples
4.124microsec 3142 samples
Test : 'ashraf aaref'
2.207microsec 3186 samples
2.200microsec 3150 samples
2.203microsec 3011 samples
2.200microsec 3214 samples
Test : 'Blindman67'
1.068microsec 3158 samples
1.060microsec 3146 samples
1.058microsec 3110 samples
1.068microsec 3143 samples
----------------------------------------------------------
Test : 'Oleander'
Mean : 4.152ms 12482 samples
Min : 4.124ms Max : 4.169ms
----------------------------------------------------------
Test : 'ashraf aaref'
Mean : 2.203ms 12561 samples
Min : 2.200ms Max : 2.207ms
----------------------------------------------------------
Test : 'Blindman67'
Mean : 1.064ms 12557 samples
Min : 1.058ms Max : 1.068ms
----------------------------------------------------------
Mean : 2.469ms Totals time : 92849.685ms 37600 samples

end of output */

// the sample function. Running this function constitutes one sample.
func : function(){
    var i;
    for (i = 0; i < 1000; i += 1) {
        digPow(Math.floor(Math.random() * 10000000),i%10);
    }
},    


// Functions all run in strict mode. 

// Test : 'Oleander'
function digPowA(n, p){
    const digits = n.toString().split('');
    const result = digits.reduce(function(acc, value, index) {
        return acc + Math.pow(value, index + p);
    }, 0);
    
    if (result % n === 0){
        return result / n;
    } else {
        return -1;
    }
}     
// Test : 'ashraf aaref'
function digPowB(n, p){
    var digits = n.toString(); //** without split should be faster**
    var result = 0;
    for(var i=0; i<digits.length; i++){
        result = result + Math.pow(digits[i], p);
        p++;
    }
    if(result % n === 0){
        return result/n;
    }else{
        return -1;
    }
}   
// Test : 'Blindman67'
function digPowC(n, p){
    var digits, result,i;
    digits = Math.floor(Math.log10(n)) + p;
    result = 0;
    var num = n;
    while(digits >= p){
        result += Math.pow((num % 10),digits--);
        num = Math.floor(num / 10);
    }
    if(result % n === 0){
        return result/n;
    }
    return -1;
}       

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

Not sure if you want feedback on the algorithm or the language, so here’s is both :)

  • Use Array.reduce instead of for as that doesn’t require you to mutate any data. Before, result and p changed on each iteration.
  • Use const instead of var as non of the variables are changed.
  • Added your examples as assert:s to verify the implementation (more for me then for you).

Hope that helps.

const assert = require("assert");

function digPow(n, p){
  const digits = n.toString().split('');
  const result = digits.reduce(function(acc, value, index) {
    return acc + Math.pow(value, index + p);
  }, 0);

  if (result % n === 0){
    return result / n;
  } else {
    return -1;
  }
}

assert(digPow(89, 1) == 1);
assert(digPow(92, 1) == -1);
assert(digPow(695, 2) == 2);
assert(digPow(46288, 3) === 51);
\$\endgroup\$
0
\$\begingroup\$

looks good for me, there are only two things I would do differently:

function digPow(n, p){
  var digits = n.toString(); //** without split should be faster**
  var result = 0;
  for(var i=0; i<digits.length; i++){
    result = result + Math.pow(digits[i], p);
    p++;
  }
  // var data = result/n; //** moved this line inside the if**
  if(result % n === 0){
    return result/n;
  }else{
    return -1;
  }
}
\$\endgroup\$

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.