DEV Community

dev.to staff
dev.to staff

Posted on

2

Daily Challenge #211 - Product Partitions

Given a natural number n, we want to know in how many ways we can express these numbers as product of other numbers.

For example, the number 18:

18 = 2 x 9 = 3 x 6 = 2 x 3 x 3 #(3 ways) 

See this example, a bit more complicated:

60 = 2 x 30 = 3 x 20 =  4 x 15 = 5 x 12 = 6 x 10 = 2 x 2 x 15 = 2 x 3 x 10 = 2 x 5 x 6 =  3 x 4 x 5 = 2 x 2 x 3 x 5 #(10 ways)

We need to implement the function prod_int_part(), that receives a number n, and outputs the total amount of different products with all the products of max length sorted in this way:

1) each product will be expressed in a list of its factors in increasing order from left to right

2) if there is more than one list-product, these lists should be ordered by the value of the first term, but if two lists have the same term then it should be ordered by the value of the second term.

Let's see some cases:
prod_int_part(18) == [3, [2, 3, 3]]
prod_int_part(60) == [10, [2, 2, 3, 5]

If we have only one list-product with the maximum length, there is no use to have it with two nested braces, so the result will be like this case:
prod_int_part(54) == [6, [2, 3, 3, 3]]

Now, let's see examples when n cannot be partitioned:
prod_int_part(37) == [0, []]
prod_int_part(61) == [0, []]

Examples

prod_int_part(60)
prod_int_part(54)
prod_int_part(37)

Enjoy!


This challenge comes from raulbc777 on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

Redis image

Short-term memory for faster
AI agents

AI agents struggle with latency and context switching. Redis fixes it with a fast, in-memory layer for short-term context—plus native support for vectors and semi-structured data to keep real-time workflows on track.

Start building

Top comments (1)

Collapse
 
mellen profile image
Matt Ellen-Tsivintzeli • Edited

Javascript

function parts(n, primeSearch=false)
{
    let factors = [...Array(n-1)].map((e, i) => i+1).filter(x => n%x == 0)
    factors.splice(0,1);
    let count = factors.length;
    if(count === 0)
    {
        return [0, []];
    }

    if(primeSearch)
    {
        return [1,[]]
    }

    let factorParts = factors.map(factor => [factor, n/factor].sort((a,b) => a-b))
        .concat(factors
                .filter(factor => parts(factor, true)[0] !== 0)
                .map(factor =>
                     {
                         let fp = parts(factor);
                         fp[1].push(n/factor);
                         return fp[1].sort((a,b) => a-b);
                     })).sort();    

    let resultFactors = [];

    for(let fli = 0; fli < factorParts.length-1; fli++)
    {
        let fl1 = factorParts[fli];
        let fl2 = factorParts[fli+1];

        if(fl1.length != fl2.length)
        {
            resultFactors.push(fl1);
            continue;
        }

        let diffsum = 0;

        for(let fi = 0; fi < fl1.length; fi++)
        {
            diffsum += fl1[fi] - fl2[fi];
        }

        if(diffsum !== 0)
        {
            resultFactors.push(fl1);
        }
    }

    resultFactors.push(factorParts[factorParts.length-1]);
    resultFactors.sort((l1, l2) => l2.length - l1.length);
    return [resultFactors.length, resultFactors[0]];
}

Warp.dev image

Warp is the #1 coding agent.

Warp outperforms every other coding agent on the market, and gives you full control over which model you use. Get started now for free, or upgrade and unlock 2.5x AI credits on Warp's paid plans.

Download Warp

👋 Kindness is contagious

Discover fresh viewpoints in this insightful post, supported by our vibrant DEV Community. Every developer’s experience matters—add your thoughts and help us grow together.

A simple “thank you” can uplift the author and spark new discussions—leave yours below!

On DEV, knowledge-sharing connects us and drives innovation. Found this useful? A quick note of appreciation makes a real impact.

Okay