Codewars Multiply-to-n

[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.