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 }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.
i don't see a better logic, however i can think of some optimisations:
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)
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 }