CAP - Editorial

CAP - UPLOADED

PROBLEM LINK

Practice

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

Practice

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