Given an positive integer n. Count total number of ways to express ‘n’ as sum of odd positive integers.
Examples:
Input: 4 Output: 3 Explanation There are only three ways to write 4 as sum of odd integers: 1. 1 + 3 2. 3 + 1 3. 1 + 1 + 1 + 1 Input: 5 Output: 5
Simple approach is to find recursive nature of problem. The number ‘n’ can be written as sum of odd integers from either (n-1)th number or (n-2)th number. Let the total number of ways to write ‘n’ be ways(n). The value of ‘ways(n)’ can be written by recursive formula as follows:
ways(n) = ways(n-1) + ways(n-2)
The above expression is actually the expression for Fibonacci numbers. Therefore problem is reduced to find the nth fibonacci number.
ways(1) = fib(1) = 1 ways(2) = fib(2) = 1 ways(3) = fib(2) = 2 ways(4) = fib(4) = 3
C++
// C++ program to count ways to write// number as sum of odd integers#include<iostream>using namespace std;// Function to calculate n'th Fibonacci numberint fib(int n){ /* Declare an array to store Fibonacci numbers. */ int f[n+1]; int i; /* 0th and 1st number of the series are 0 and 1*/ f[0] = 0; f[1] = 1; for (i = 2; i <= n; i++) { /* Add the previous 2 numbers in the series and store it */ f[i] = f[i-1] + f[i-2]; } return f[n];}// Return number of ways to write 'n'// as sum of odd integersint countOddWays(int n){ return fib(n);}// Driver codeint main(){ int n = 4; cout << countOddWays(n) << "\n"; n = 5; cout << countOddWays(n); return 0;} |
Java
// Java program to count ways to write// number as sum of odd integersimport java.util.*;class GFG { // Function to calculate n'th Fibonacci numberstatic int fib(int n) { /* Declare an array to store Fibonacci numbers. */ int f[] = new int[n + 1]; int i; /* 0th and 1st number of the series are 0 and 1*/ f[0] = 0; f[1] = 1; for (i = 2; i <= n; i++) { /* Add the previous 2 numbers in the series and store it */ f[i] = f[i - 1] + f[i - 2]; } return f[n];}// Return number of ways to write 'n'// as sum of odd integersstatic int countOddWays(int n){ return fib(n);}// Driver codepublic static void main(String[] args) { int n = 4; System.out.print(countOddWays(n) + "\n"); n = 5; System.out.print(countOddWays(n));}}// This code is contributed by Anant Agarwal. |
Python3
# Python code to count ways to write# number as sum of odd integers# Function to calculate n'th # Fibonacci numberdef fib( n ): # Declare a list to store # Fibonacci numbers. f=list() # 0th and 1st number of the # series are 0 and 1 f.append(0) f.append(1) i = 2 while i<n+1: # Add the previous 2 numbers # in the series and store it f.append(f[i-1] + f[i-2]) i += 1 return f[n]# Return number of ways to write 'n'# as sum of odd integersdef countOddWays( n ): return fib(n)# Driver coden = 4print(countOddWays(n))n = 5print(countOddWays(n))# This code is contributed by "Sharad_Bhardwaj" |
C#
// C# program to count ways to write// number as sum of odd integersusing System;class GFG { // Function to calculate n'th // Fibonacci number static int fib(int n) { /* Declare an array to store Fibonacci numbers. */ int []f = new int[n + 1]; int i; /* 0th and 1st number of the series are 0 and 1*/ f[0] = 0; f[1] = 1; for (i = 2; i <= n; i++) { /* Add the previous 2 numbers in the series and store it */ f[i] = f[i - 1] + f[i - 2]; } return f[n]; } // Return number of ways to write 'n' // as sum of odd integers static int countOddWays(int n) { return fib(n); } // Driver code public static void Main() { int n = 4; Console.WriteLine(countOddWays(n)); n = 5; Console.WriteLine(countOddWays(n)); }}// This code is contributed by vt_m. |
PHP
<?php// PHP program to count ways to write// number as sum of odd integers// Function to calculate n'th// Fibonacci numberfunction fib($n){ // Declare an array to // store Fibonacci numbers. $f = array(); $i; // 0th and 1st number of the // series are 0 and 1 $f[0] = 0; $f[1] = 1; for($i = 2; $i <= $n; $i++) { // Add the previous 2 // numbers in the series // and store it $f[$i] = $f[$i - 1] + $f[$i - 2]; } return $f[$n];}// Return number of ways to write 'n'// as sum of odd integersfunction countOddWays( $n){ return fib($n);} // Driver Code $n = 4; echo countOddWays($n) , "\n"; $n = 5; echo countOddWays($n); // This code is contributed by anuj_67.?> |
Javascript
<script>// Javascript program to count ways to write// number as sum of odd integers// Function to calculate n'th Fibonacci numberfunction fib(n) { /* Declare an array to store Fibonacci numbers. */ let f = []; let i; /* 0th and 1st number of the series are 0 and 1*/ f[0] = 0; f[1] = 1; for (i = 2; i <= n; i++) { /* Add the previous 2 numbers in the series and store it */ f[i] = f[i - 1] + f[i - 2]; } return f[n];} // Return number of ways to write 'n'// as sum of odd integersfunction countOddWays(n){ return fib(n);} // Driver code let n = 4; document.write(countOddWays(n) + "<br/>"); n = 5; document.write(countOddWays(n)); // This code is contributed by code_hunt.</script> |
Output:
3 5
Note: The time complexity of the above implementation is O(n). It can be further optimized up-to O(Logn) time using Fibonacci function optimization by Matrix Exponential.
Auxiliary Space: O(n)
This article is contributed by Shubham Bansal. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
