Home / Questions / 296899
Accepted
RazerJs
Asked: 2020-09-28 13:49:50 +0800 CST 2020-09-28 13:49:50 +0800 CST

Get the largest possible multiplication of the decomposition of a javascript number

  • 772

The problem is the following; given a number n (positive integer <100) this is broken down into non-equal numbers that add up to n and whose multiplication is the greatest possible.

Examples:

  • n=5 result 6 because 2 x 3=6
  • n=8 result 15 because 5 x 3 = 15
  • n=10 result 30 because 2 x 3 x 5 = 30
  • n=15 result 144 because 2 x 3 x 4 x 6 = 144

To obtain the greatest multiplication, the numbers must be decomposed, but in the same way these cannot be repeated.

This is what I have done:

The function esPrimo()returns me trueor falseif the number that is passed to it is prime, I use it to know if I can divide the number into more addends.

The function dividirNumero()divides the number into its addends and returns the largest multiplication among them.

And the function maximumProduct()is the one that should be called recursively to continue dividing the numbers, and check that they don't repeat themselves, but I don't know how to do this part.

<!--   MIRAR ESTA FUNCION -->

function maximumProduct(n) {
    let numeros = dividirNumero(n)
    let multiplicadores = []
    let aSimplificar = [] // aqui estan los que se pueden simplificar para hallar la mayor multiplicacion
    numeros.map(n => {
        return esPrimo(n) ? multiplicadores.push(n) : aSimplificar.push(n)// esta parte es la que se pudiera llamar recursiva
    })
    console.log(aSimplificar);
    return multiplicadores.reduce((a, b) => a * b)
}

function dividirNumero(n) {
    let arr = []
    let mayorMultiplicacion = 0
    let par = []
    for (let i = 1; i < n; i++) {
        arr.push(i)
    }

    for (let i = 0; i < arr.length - 1; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[i] + arr[j] == n) {
                if (arr[i] * arr[j] > mayorMultiplicacion) {
                    mayorMultiplicacion = arr[i] * arr[j]
                    par.pop()
                    par.push([arr[i], arr[j]])
                }
            }
        }
    }
    return par[0]
}

function esPrimo(x) {
    const primos = [2, 3, 7, 11, 13, 17, 19, 23, 29];
    if (x < 2) {
        return false
    } else if (primos.indexOf(x) > -1) {
        return true
    } else if (primos.some(primo => x % primo == 0)) {
        return false
    } else {
        if (x <= primos[primos.length - 1] * 2) {
            return true
        } else {
            let test = true;
            for (let i = primos[primos.length - 1] + 1; i <= Math.floor(x / 2); i++) {
                if (x % i === 0) {
                    test = false;
                    break;
                }
            }
            return test;
        }
    }
}


console.log(maximumProduct(20));

javascript

1 Answers

  1. Best Answer

    An alternative way to solve the problem could be to iterate through the options as a tree with multiple nodes.

    The idea is the following:

    Taking the number 10 as an example.

    The first possible values ​​in the series are the numbers between 2 and n-2.

    2,3,4,5,6,7,8

    1 and n-1 (9) are not taken into account since their product is even less than the original number.

    Then the next values ​​of the series are given according to the first value, these values ​​added to the previous one must be less than or equal to n, and they will be numbers greater than the previous numbers, therefore they will not be equal:

    para 2: 3,4,5,6,7,8
para 3: 3,4,5,6,7
para 4: 5
para 5: -
...
para 8: -

    If there are no numbers that can be added to the series, it is verified if the sum is equal to n, if so it is added to the list of possible solutions, otherwise it is discarded.

    In the previous level no series was added.

    Then continue with the next level:

    para 2,3: 4,5
para 2,4: -
...
para 2,8: -
para 3,4: -
para 3,5: -
...
para 3,7: -

    In this are added 2,8and3,7

    and then the next level is like this;

    2,3,4: -
2,3,5: -

    At this level the 2,3,5.

    Finally, the multiplication of each series is done to find the one that generated the largest product:

    2 * 8 = 16
3 * 7 = 21
2 * 3 * 5 = 30 <=

    and then the one shown is the series with the largest product.

    The code is working as follows:

    var posibles;

function maxApoyo(n, r, a) { 
  for(var i=r+1; i<n-1 ;i++){  
    var suma = [...a,i].reduce((a,s)=>a+s); 
    suma==n ? posibles.push([...a,i]) : suma<n ? maxApoyo(n, i, [...a,i]) : 0 
  }
}

function maximumProduct(n) {
  var max=0;
  var pmax=0;
  posibles = [];
  maxApoyo(n, 1, [], posibles);
  // console.log(posibles);
  for(p in posibles){
    mul = posibles[p].reduce((a,m)=>a*m);
    if(mul>max){
      pmax=p;
      max=mul;
    }
  }
  return `n = ${n} resultado ${max} por que ${posibles[pmax].join('*')}=`+max;
}

console.log(maximumProduct(5));
console.log(maximumProduct(8));
console.log(maximumProduct(10));
console.log(maximumProduct(15));
console.log(maximumProduct(29));
console.log(maximumProduct(36));
console.log(maximumProduct(59));
    .as-console-wrapper { max-height: 100% !important; top: 0; }

    In this code, the possible solutions are placed in the array posibles, then the function maxApoyo()is a recursive function that simulates the traversal of a multiple tree, and the function maximumProduct()checks the most optimal series and displays the result.

    I hope that this contribution will be useful to understand how algorithms work with trees and help solve similar problems, greetings.

    • 4