First of all, it is a difficult problem or an easy problem ?
Write a function
long count(String N, int M) which returns the number of permutations which are divisible by M.Example :-
String N = "2753" and
int M = 5 Returns: 6
The permutations of 2753 that are divisible by 5 are 2375, 2735, 3275, 3725, 7235 and 7325.
and M can have values from 1 to 50.
The only method I can think of is :-
1.Generate all permutations for the string N and store it somewhere like a list or an array.
2.For each element of the list or array, divide by M...IF IT IS DIVISIBLE, increment the counter.
3.Return that counter.
Fine. But how do we do step -1
7 comments:
You don't need to store the numbers anywhere. You just need to count the number of permutations. Now, if you want all permutations which are divisible by 5, you know that the unit's digit has to be 5. Now, the remaining 3 positions have to be filled up by the remaining 3 numbers (which are 2,7 and 3). This means that you are looking at a problem of 3p3 = 3! = 6. You didn't need to actually store those numbers.
Yeah but thats only for the number "5"...
What would we do for say "7" or "43" ?
But as you said, we may not STORE the nos. ....there might be a way of generating the permuted numbers on the fly and checking divisiblity....
Yes I agree with you. We could check for divisibility and then increment the counter without storing the number.
I think to generate the permutation, you recurse and don't know what later. One way to generate permuations of say 1,2,3 is to
Keep 1.
Place 2 on either side of 1. { (1,2), (2,1) }
Do the same for 3 for each element of the above set. { So (3,1,2),(1,3,2),(1,2,3) will be got from (1,2) by adding 3 }. Similarly for (2,1).
Generating permuations of a reasonably large set of numbers is NP-hard. Additionally divisibility tests for prime numbers like 19, etc are pretty hard. Its a difficult problem, from a computational viewpoint.
http://portal.acm.org/citation.cfm?id=356692
For N numbers, we have N! permutations.
N! > 2**N ( for N >= 4 ).
So worse than exponential.
Between, I couldn't get how you would frame this problem as a decision problem.
Post a Comment