CAP - UPLOADED
PROBLEM LINK
Author: Abishek S
Editorialist: Kairav Shah
DIFFICULTY
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.
PROBLEM LINK
Author: Abhishek S
Editorialist: Kairav Shah
DIFFICULTY
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