CODEWITHSUNDEEP
java
Zohra Khan
Zohra Khan

Reputation: 5302

What is the highest power of A that divides N factorial?

I am trying to solve this problem on codefights.com by finding out the largest prime factor and dividing the number with the powers of prime factor.

int highestPower(int N, int A) {
int B =A, j=0,c=0, p=0,x;

for(int i = 2; i<=A; i++) {
    if( A%i == 0) {
        p = i>p ? i:p;
        A/=i;
        --i;
    }
    if(i*i > A && B==A) {
        p = B;
        break;
    }
}

for(;(x = N/((int)Math.pow(p,++j))) > 0; )
    c+=x;
return c;

}

Input:

0<N<10^9
1<A<10^9

But this approach will fail for some test cases.One such test case is:

N:100
A:1024
Output:97
Expected Output:9

Any suggestions on how to solve this problem?

Upvotes: 0

Views: 515

Answers (1)

Ruslan Batdalov
Ruslan Batdalov

Reputation: 793

The last for loop calculates the power of p that divides N, but if the power of p in factorisation of A is greater than one, it is not the same as the needed answer. In the given example, you calculate that 2^97 divides 100!, but it is not about what you were asked. At least you should divide by the power of p in factorisation of A (10 in this case), but I do not know whether it will be enough in the general case.

Upvotes: 1

Related Questions