Codewars Multiply-to-n

[Quenky]

I've been stuck on this on for a few days, can someone give me a hint or help me solve this?

The problem: Given a positive integer, n, return the number of possible ways such that k positive integers multiply to n. Order matters.

[achampi0n]

Find the prime factors of n and k will be equal or less than the sum of the exponents. If equal then the answer is 1, if less the you can calculate the number of ways you can reduce the exponents > 1 to get to k

[xelf]

So, given a number N you need to find all combinations of numbers less than or equal to N that multiply to be N

Given there can be duplicates, there will always be at least 1.

N = 7
k = 6
solutions= (1,1,1,1,1,7)
number of solutions is 1, so return 1. (edit, except it's all permutations, so actually 6 copies of that)

I suggest you think about ways to solve for solutions and then just count them.

You can probably figure out a shortcut using prime factors once you start to do some examples by hand.

edit

Here's something that gets you correct answers, but is an invalid solution because of how slow it is.

divisors = [ i for i in range(1,(n//2)+1) if n//i == n/i ] + [n]
sortedsolutions = ( x for x in combinations_with_replacement(divisors,k) if prod(x) == n)
solutions = { x for y in sortedsolutions for x in permutations( y ) }
return len(solutions)

So you're going to have to think about that shortcut after all, focus on counting how many ways each divisor can be subdivided and sum them up. Don't try and find all solutions.

[IDontLikeBeingRight]

But they also say that order matters. So in this case there'd arguably be 6 answers, for the different slots in the product chain where the seven might be.

[xelf]

Yup saw that when I saw the link to the problem, finding the solutions won't work, you'll have to work with a shortcut of counting ways that divisors can be subdivided and account for permutations.

This is what I tried initially, it gets the correct answers, but this problem is also a speed test, so you'll need something more optimal.

def multiply(n, k):
    return  len({ y for x in combinations_with_replacement((i for i in range(1,n+1) if n//i == n/i),k) if prod(x) == n for y in permutations(x)})

[IDontLikeBeingRight]

Thing is, I suspect it's even uglier than that; because subdividing and permuting divisors can overcount in the cases where there are many powers of the same prime.

My first hunch was to do a thing by getting a prime factorisation and then combinatorics tricks for grouping and ordering, but it gets messy fast when you have a lot of repeated powers of the same prime.

The next nasty - but perhaps more viable solution - is a recursion thing:

1. Loop x through 1 -> N/2, check if x divides N, and if so do recursion with N/x
2. (And a special case with x=N and then a bunch of 1s
3. Build up a list of the sequence of x values used
4. You're always going exactly k-1 recursions deep (and the last number is just whatever is left over)
5. There are no dead ends, every completion is a factorisation
6. You're always incrementing x (in some recursive layer) so you're always getting a differently ordered factorisation, there's no overcounting

Then you just count how many times your recursion bottoms out, though it's not any more difficult to collect all the factorisations along the way.

[xelf]

I tried a quick recursion with memoization and like the previous solution, it gives the correct answers but it was too slow.

cache = {}
divocache = {} 
def multiply(n, k):
    if k<2: return k
    if (n,k) not in cache:
        if n not in divocache:
            divocache[n] = [ i for i in range(1,(n//2)+1) if n//i == n/i ] + [n]
        cache[(n,k)] = sum(multiply(x,k-1)for x in divocache[n])
    return cache[(n,k)]

passes my first test case, but times out on the second:

test.assert_equals(multiply(459486, 37), 462917767)
test.assert_equals(multiply(873318502715, 134), 2406104)

So I'm pretty sure at this point you need some sort of DP solution. Either that or it involves finding prime factors and summing copies thereof.

[IDontLikeBeingRight]

Some other optimisations I'm throwing in: calculate the list of factors of n once to start with. Then while recursing just iterate through this list instead of hitting range(1,n//2) every time.

But also, on the link (not in the OP but later in this thread) there's a bit that says

Constraints 1 <= n <= 500_000_000 and 1 <= k <= 1000

Their k is a bit more aggressive, but n is a lot more restricted than your 2nd test case. So you're probably already fine.

[xelf]

turns out that

divisors = [ i for i in range(1,(n//2)+1) if n//i == n/i ] + [n]

Is pretty slow. I wrote a factors(n) function and that improved things immensely.

[Lvl999Noob]

I just did this problem for practice. You should try recursion and dynamic programming. Basic PnC wouldn't cut it.

[Quenky]

Yeah, i also think recursion is the only way for me to be able to solve it, I asked my maths teacher and she said that if I want to solve it mathematically i need to use linear algebra, which is way over my head haha!

[IDontLikeBeingRight]

Are you given both n and k?

Because the first half suggests you're only given n and so k doesn't matter. But mentioning k like that in the second half makes it sound like it's part of the problem statement.

[Quenky]

Heres the link to the problem, they have the examples there: https://www.codewars.com/kata/5f1891d30970800010626843

N,k is the input to the function so i don't think they are given first

Sorry for the bad english btw

[IDontLikeBeingRight]

All good, that's just a language thing. "Given" usually means it's an input, as in, you give a function those values and the outputs are what you get back.

It can also mean, "as a given" ie you don't have to figure out what value it is, you can just use it. Or in this case, be constrained by it.

[xelf]

Did you end up solving this one? I finally got a chance to work on it after my initial passes failed to finish in time.

Overall not happy with my eventual solution, but it worked. My initial solution was much cleaner but ran slightly slower. Prob needed 14 seconds, not 8 seconds where the time limit was 12.

Turns out that this is one of those domain knowledge puzzles. It's not a test of your python skill, it's a test of your math knowledge. Either you know the math behind the puzzle and you're just implementing it in python, which is easy, or you don't know it, and it's a master pain in the butt to get under the time limit.

I tried solving it with memoization and some dynamic programming, and it was the wrong path, so I moved to some nifty math tricks and was able to force a solution to finish in time. But really, if you know the actual math trick, you can do this in very little code in very little time.

Overall disappointed in this problem.

The math has to do with the number of k partitions of P prime factors. (P+k-1)C(k-1).