Interview Question
- 0of 0 votes
AnswerWe are given a list of N integers and another positive integer K. We need to compute the number of ways in which the product P of the
- sowjanyanani16 July 22, 2018 in United States
given N integers can be expressed as a product of K positive integers (not
necessarily distinct). The order of the factors in the expression is not
important. For example, 1 x 2 x 3 and 2 x 3 x 1 are not counted as different
ways of expressing 6 as a product of three integers.
Input Format
The first line contains two space-separated integers, N and K
The next line contains N-space separated integers
Output
One line containing the number of ways in which the product of the N
integers can be expressed as a product of K positive integers
Example:
Input
2 3
4 16
Output
7
Explanation
The product is 64. This can be expressed as a product of three integers in
the following ways:
1 x 1 x 64
1 x 2 x 32
1 x 4 x 16
1 x 8 x 8
2 x 2 x 16
2 x 4 x 8
4 x 4 x 4| Report Duplicate | Flag | PURGE
You only need to know P and K. The list of N integers is irrelevant to the problem.
- adr July 23, 2018The first part is to factor P into primes. Then, if all the elements in the resultant list of prime factors are unique, there is a simple combinatorical solution: 1+sum_i=1..K-1 (C(i, L-1)), where C(k,n) = n!/k!(n-k)! and L is length of the list of primes.
I find the general case hard though. When we have duplicates in the list of primes (think of [2, 2, 2, 2, 2] where [2,2],[2,2,2] and [2,2,2],[2,2] result in the same terms, 4*8 = 8*4) I can't think of any better way than to iterate over all 2-way, 3-way, .. K-way splits of the list of prime factors, compute the resultant product terms, and count ignoring repetitions.