harshalpamecha3's blog

By harshalpamecha3, history, 4 months ago, In English
 
 
 
 
  • Vote: I like it
  • -5
  • Vote: I do not like it

»
4 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Do you recall the combinactories problem in your high school, where there are total $$$n$$$ items and $$$n1$$$, $$$n2$$$, $$$n3$$$,$$$...$$$ different items in a bag. Then what are the different combinations of choosing items from the bag. It was- ($$$n!$$$)/($$$n1!$$$*$$$n2!$$$*$$$n3!$$$$$$...$$$) Similarly, consider this problem same too. You have been given a number n and you have n different(maybe same) digits. Find the total ways to choose is. Simply find the frequency of all digits and find ($$$n!$$$)/($$$n1!$$$*$$$n2!$$$*$$$n3!$$$$$$...$$$), where $$$n1$$$, $$$n2$$$, $$$n3$$$ are the frequencies.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But here constraint are high so how to calculate factorial???

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Precompute

      Code
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Basically you can be given a number having maximum of 10^5 digits. Each character(digit) can only be from 0 to 9. So, you store frequency of each digit in an array of size 10. Now, again when you apply the permutation formula you may have to calculate factorial of 10^5 but we need to report answer as modulo mod(prime number given). So, basically all of your precomputed factorial values will not go beyond mod value because you will be storing them by taking modulo with respect to mod. Similarly you have to store inverse-factorial values also upto 10^5 modulo mod(read about Using FERMET's Little Theorem for finding Modular Multiplicative Inverse if you dont know yet). Doing these modular arithmatic calculations you can evaluate the above mentioned expression. Time and Space Complexities would be -> O(n) where n = 10^5.