how to solve this equation efficiently?

general
, , ,
1

please help me solve this equation in O(1) or O(logn) time.
1<=n<=10^18

equation:

(n-1) + (n-2)(n-3)/2! + (n-3)(n-4)(n-5)/3! + (n-4)(n-5)(n-6)(n-7)/4! +…+ (n-(n/2))(n-(n/2+1))…(n-(n-1))/(n/2)!

or this eqvivalent combinatric equation

sum of C(n-k,k) for all 1<=k<=floor(n/2)

1 Like
2

let dp[n] be ans for n

this is recurrence

dp[n]=dp[n-1]+dp[n-2]+1;

dp[2]=1
dp[3]=2

calculate using expo…

1 Like
3

Think about what C(n-k,k) looks like in Pascal’s triangle. The sums you have are essentially (barring a leading term C(n,0)) sums along diagonals of Pascal’s triangle

\begin{array}{ccccccccc} & & & & {\color{red}1}\\ & & & {\color{green}1} & & {\color{blue}1}\\ & & {\color{blue}1} & & {\color{magenta}2} & & {\color{orange}1}\\ & {\color{magenta}1} & & {\color{orange}3} & & 3 & & 1\\ {\color{orange}1} & & 4 & & 6 & & 4 & & 1\\ \end{array}

which turns out to be Fibonacci numbers

{\color{red}1}, {\color{green}1}, {\color{blue}2}, {\color{magenta}3}, {\color{orange}5}, \ldots

for which you can apply the usual fast techniques for calculating Fibonacci numbers (like matrix exponentiation).

2 Likes
4

thank you… got it.

5

Is n even ??

1 Like
6

not necessary.

7

shouldn’t the sequence be like 1,1,2,4,…

As for n=4:-it is 3C1+2C2=4?

1 Like
8

Like I wrote, the sum asked about is essentially Fibonacci numbers. However it’s missing the leading term C(n,0). Without the leading term the sequence is just Fibonacci numbers minus one: 0,0,1,2,4,7,12,\ldots.

Compare (python code, implement choose yourself)

[sum(choose(n-k,k) for k in range(1,n//2+1)) for n in range(0,10)]
-> [0, 0, 1, 2, 4, 7, 12, 20, 33, 54]

with

[sum(choose(n-k,k) for k in range(0,n//2+1)) for n in range(0,10)]
-> [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
1 Like
9

yeah yeah right… :slight_smile:

1 Like
10

@algmyr
@vivek_1998299
can you help me solve this question?
problem link: Programming Problems and Competitions :: HackerRank

i have try lot but did’t got correct formula. please help me.