 # CAP - Editorial

Practice

Author: Abishek S
Editorialist: Kairav Shah

Medium

# PREREQUISITES

Number Theory, Fibonacci Series

# EXPLANATION

The problem is quite simple, yet disguised as a hard one. It simply asks what is the number of ways to write a number N as a sum of odd numbers. And number of such ways is given by the famous Fibonacci series.

We can prove it by considering f(n) to be the number of ways to write n as sum of odd numbers. Then given f(n-1), we can add a 1 to the sum to form n, or given f(n-2) we can add 2 to the last number in all the summations that form n-2 to form n (Adding 2 to an odd number gives another odd number only).

Thus f(n) = f(n-1) + f(n-2), which is the fibonacci series. Also, to pass the testcases without TLE, precompute the fibonacci series for all n till the maximum value of n and store it.

Practice

Author: Abhishek S
Editorialist: Kairav Shah

Medium

# PREREQUISITES

Number Theory, Fibonacci Series

# EXPLANATION

The problem is quite simple, yet disguised as a hard one. It simply asks what is the number of ways to write a number N as a sum of odd numbers. And number of such ways is given by the famous Fibonacci series .

We can prove it by considering f(n) to be the number of ways to write n as sum of odd numbers. Then given f(n-1), we can add a 1 to the sum to form n, or given f(n-2) we can add 2 to the last number in all the summations that form n-2 to form n (Adding 2 to an odd number gives another odd number only).

Thus f(n) = f(n-1) + f(n-2), which is the fibonacci series. Also, to pass the testcases without TLE, precompute the fibonacci series for all n till the maximum value of n and store it.

Markdown 1020 bytes 171 words 19 lines Ln 15, Col 177

HTML 681 characters 161 words 12 paragraphs