×

# how to solve this equation efficiently?

 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) asked 14 Oct '18, 16:58 42●5 accept rate: 7% 1 Is n even ?? (14 Oct '18, 18:57) not necessary. (14 Oct '18, 21:13)

 2 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). answered 15 Oct '18, 02:59 7★algmyr 1.2k●13 accept rate: 37% 1 shouldn't the sequence be like 1,1,2,4,.. As for n=4:-it is 3C1+2C2=4? (15 Oct '18, 11:45) 1 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]  (15 Oct '18, 15:11) algmyr7★ 1 yeah yeah right... :) (15 Oct '18, 15:47) @algmyr @vivek_1998299 can you help me solve this question? problem link: https://www.hackerrank.com/contests/moodys-analytics-2018-women-in-engineering/challenges/combination-of-digits i have try lot but did't got correct formula. please help me. (15 Oct '18, 21:42)
 1 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... answered 15 Oct '18, 00:25 1.6k●2●9 accept rate: 23%
 0 thank you.. got it. answered 15 Oct '18, 21:38 42●5 accept rate: 7%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,237
×1,176
×868
×42
×23

question asked: 14 Oct '18, 16:58

question was seen: 386 times

last updated: 16 Oct '18, 00:42