CODEWITHSUNDEEP
algorithmmath
user3159871
user3159871

Reputation: 1

Permutation of lengthy string

The following is the question I tried solving :

A string contains characters from '0' to '9'. Now find out the total possible permutations for this string. Since the number can be very large, output the number modulus 10^9+7.

Input : First line represent the number of test cases(T). Each test case contains a string of digits. Output : For each test case output the required result.

Constraints : T<=100. Length of String <= 1000

So, I assumed that I just need to find out len! where len is the length of the string. My code for finding out the factorial is as follows : 

long long int fact(long long int n)
{
if(n<=1)
return 1;
else
return (len * fact(len-1))%1000000007;
}

But I keep getting WA for this code. Disregarding the Output format issues, is the above code for finding out the factorial correct? Or should I use a different approach?

NOTE: I also changed the algorithm so that repetition of certain characters is handled by dividing the answer by the product of factorial of the occurrences of each character.

Upvotes: 0

Views: 221

Answers (1)

U2EF1
U2EF1

Reputation: 13259

(a) It's not just n!, there are only 10 possible digits (and possibly fewer in your string). If I gave you the string "22", there would only be 1 permutation.

(b) The ultimate number is still going to be very large, you aren't going to be able to calculate it without bignums. But since you only need the number modulo a reasonably small number, you can use identities for mod to keep intermediate numbers small. Of particular use will be the fact that a * b % k = ((a % k) * (b % k)) % k.

Hopefully this is enough to go on without spoiling it.

Upvotes: 4

Related Questions