## 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

**Country:**United States

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

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.