CODEWITHSUNDEEP
javascriptlogarithm
Max Voisard
Max Voisard

Reputation: 1942

Find simplest base and its exponent given product

Given a product, I want to find the most simplified base and its corresponding exponent. For instance, a product of 343 would yield a base of 7 and exponent of 3. If a certain product returns multiple sets of bases and exponents, only the simplest base is considered. For example, the product of 64 would return a base of 2 and exponent of 6, and eliminate the higher combinations of base 4 and exponent 3 and base 8 and exponent 2.

Now, I've already written a program that works for this scenario. However, it seems to be relatively unorthodox and can take a long time to compile given high numbers for the product argument specified. Is there a better and more efficient way of writing the function, possibly by using logarithms? I can't seem to find anything on this type of programming problem.

function findBaseAndExponent(product) {
   product = Math.round(product);
   var base = 0;
   var exp = 0;
   var abort = false;
   for (var i = 1; i <= product && !abort; i++) {
       for (var j = 1; j <= product && !abort; j++) {
          const currProd = Math.pow(i, j);
          if (currProd == product) {
             base = i;
             exp = j;
             abort = true;
          }
          if (currProd > product){
             break;
          }
      }
   }
   if (base == product && exp == 1) {
      base = "N/A";
      exp = "N/A";
   }
   return { "base": base, "exponent": exp };
}

console.log(findBaseAndExponent(343)); // Output: { base: 7, exponent: 3 }
console.log(findBaseAndExponent(64)); // Output: { base: 2, exponent: 6 }
console.log(findBaseAndExponent(41)); // Output: { base: N/A, exponent: N/A }

Upvotes: 2

Views: 303

Answers (3)

Max Voisard
Max Voisard

Reputation: 1942

This code checks if a number is a base of a product, not a factor of the product. You see, for a product like 42, there is no base and exponent that match it, yet there will be divisible integers that go into it - like 2, 6, 7, and 21. We don't care about any of those factors being an integer, but rather a base evaluating to an integer.

var isRoot = function (n, root) { return Number.isInteger(getBase(n, root)); };
const getBase = (n, root) => parseFloat(Math.pow(n, 1 / root).toFixed(3));
const findExponent = (product, exponent) => ({
    base: getBase(product, exponent),
    exponent
});
function findBaseAndExponent(product) {
    for (var i = Math.ceil(Math.sqrt(product)); i >= 2; i--) {
        if (isRoot(product, i)) return findExponent(product, i);
    }
    return { base: null, exponent: null };
}

console.log(findBaseAndExponent(343)); // Output: { base: 7, exponent: 3 }
console.log(findBaseAndExponent(64)); // Output: { base: 2, exponent: 6 }
console.log(findBaseAndExponent(42)); // Output: { base: null, exponent: null }

Upvotes: 0

Xavier B.
Xavier B.

Reputation: 543

i don't see a better logic, however i can think of some optimisations:

  • you should let i go from 2 to Math.max(2, Math.floor(Math.sqrt(product)))

Not from 1 because Math.pow(1, <something>) will always be equal to 1

there is no positive integer N = Math.pow(a, b) where a and b are positive integers greater than 1 with b > sqrt(N)

Upvotes: 1

CertainPerformance
CertainPerformance

Reputation: 370819

The problem looks to reduce to finding the first number that divides the product (starting with the lowest possible first), then finding how many times it does.

A simple and more efficient way than yours would be to start at 2, then check 3, then increase by 2 for each following iteration, up until reaching the square root of the product. It's not the most efficient, but it's better and easy to implement.

const isDivisible = (a, b) => Number.isInteger(a / b);
const log = (n, base) => Math.log(n) / Math.log(base);
const findExponent = (product, base) => ({
  base,
  exponent: Math.round(log(product, base))
});
function findBaseAndExponent(product) {
  if (isDivisible(product, 2)) return findExponent(product, 2);
  for (let i = 3, limit = Math.floor(Math.sqrt(product)); i <= limit; i += 2) {
    if (isDivisible(product, i)) return findExponent(product, i);
  }
  return { base: null, exponent: null };
}

console.log(findBaseAndExponent(343)); // Output: { base: 7, exponent: 3 }
console.log(findBaseAndExponent(64)); // Output: { base: 2, exponent: 6 }
console.log(findBaseAndExponent(41)); // Output: { base: N/A, exponent: N/A }

Starting with a list of prime numbers and iterating over it instead of iterating over all odd numbers would help, if that's allowed by the constraints you're under.

Upvotes: 3

Related Questions