darkworld1's blog

Is there any efficient way to find out this ?
By darkworld1, history, 4 years ago, In English

you have given N. you need to find out C(n,1*1)+C(n,2*2)+C(n,3*3)+c(n,4*4) + .....
Here c(n,r) = n!/((n-r)!*(r)!)
one way is find C(n,i*i) for all i between 1 <= i <= sqrt(n)
. Is there exist any efficient solution than this ??

  • Vote: I like it
  • +13
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What are limits on n?

→ Reply
»
4 years ago, # |
← Rev. 9   Vote: I like it +14 Vote: I do not like it

Because

$$$1 \leq n \leq 10^6$$$

If there is a prime modulo you can use Modular Inverse with O(n) precalculation finding Factorial[] and Inverse_Factorial[]

The formula:

$$$C(n, k) = n! / ((n — k)! \times k!) = n! \times inverse(n-k)! \times inverse(k)! = Factorial[n] \times Inverse\_Factorial[n — k] \times Inverse\_Factorial[k]$$$

Then you can calculate the rest in O(sqrt n)

Total time complexity: O(n)

Total space complexity: O(n)

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't think there exist any algo better than this one. Sqrt(N) + O(N) will be best probably.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 6   Vote: I like it +13 Vote: I do not like it

    Actually, you can solve this problem in $$$O(\sqrt{n} \cdot \log^3 n)$$$ time (I suppose that we want to find this value modulo some relatively small prime $$$p$$$, where by "relatively small" I mean $$$p = n^{O(1)}$$$).

    The main idea is the same as in the standard algorithm for calculating $$$n!$$$ in $$$O(\sqrt{n} \log^2 n)$$$ time, which is reproduced in the spoiler below.

    Calculating n! quickly via multi-point evaluation

    Denote $$$k := \lfloor \sqrt{n} \rfloor$$$. Our problem can be reduced to calculating two factorials ($$$n!$$$ and $$$(n - k^2)!$$$) and two instances of "calculate the products on contiguous ranges of integers with lengths $$$1$$$, $$$3$$$, $$$5$$$, $$$\ldots$$$, $$$(2k + 1)$$$" (for example, $$$(i^2)! = ((i-1)^2)! \times ((i^2 - 2i + 2) \cdot \ldots \cdot (i^2 - 1) \cdot (i^2))$$$). This problem can be reduced to two instances of "calculate the products on contiguous ranges of integers with lengths $$$0$$$, $$$1$$$, $$$2$$$, $$$\ldots$$$, $$$k$$$").

    Okay, let's solve the latter problem recursively. We want to calculate $$$s_1$$$, $$$s_2 \cdot (s_2 + 1)$$$, $$$\ldots$$$, $$$s_\ell \cdot (s_\ell + 1) \ldots (s_\ell + \ell - 1)$$$ for some integers $$$s_i$$$. Suppose for simplicity that $$$\ell$$$ is odd and $$$\ell = 2m+1$$$. Consider the polynomial $$$P(x) = x \cdot (x + 1) \cdot (x + m)$$$. We can find $$$P(s_{m + 1})$$$, $$$P(s_{m + 2})$$$, $$$\ldots$$$, $$$P(s_{\ell})$$$ in $$$O(\ell \log^2 \ell)$$$ time by the same multi-point evaluation trick. It remains to find some products on ranges with lengths $$$1$$$, $$$2$$$, $$$\ldots$$$, $$$m$$$, $$$(m + 1) - (m + 1) = 0$$$, $$$(m + 2) - (m + 1) = 1$$$, $$$\ldots$$$, $$$(2m + 1) - (m + 1) = m$$$. Thus, we reduced our problem to two smaller problems (for $$$m$$$ ranges instead of $$$\ell$$$). Therefore, the time complexity satisfies the reccurence $$$T(\ell) = 2T(\ell/2) + O(\ell \log^2 \ell)$$$. Hence, $$$T(\ell) = O(\ell \log^3 \ell)$$$.

    Finally, the whole algorithm takes $$$O(T(k)) = O(\sqrt{n} \cdot \log^3 n)$$$ time.

    P. S. I wouldn't be surpised if it is possible to shave the extra logarithm (as compared to calculating $$$n!$$$) off somehow.

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

      Kaban-5 for N <= 10^6, O(N) will be better than O(sqrt(N)*log3N). and also the mentioned solution need much constant factor optimisations. however I believe it might work for larger constraints :) THanks

      → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

As one of the comments already mentions, using the inverse modulo of the factorial in the denominator would work. I wrote code for this problem in which I had to find the sum of combinations, although not the same ones.

Code for calculating nCr in O(1) with O(n) precomputations
→ Reply