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