Number of ways to represent a number as sum of k fibonacci numbers
Given two numbers N and K. Find the number of ways to represent N as the sum of K Fibonacci numbers.
Examples:
Input : n = 12, k = 1 Output : 0 Input : n = 13, k = 3 Output : 2 Explanation : 2 + 3 + 8, 3 + 5 + 5.
Approach: The Fibonacci series is f(0)=1, f(1)=2 and f(i)=f(i-1)+f(i-2) for i>1. Let’s suppose F(x, k, n) be the number of ways to form the sum x using exactly k numbers from f(0), f(1), …f(n-1). To find a recurrence for F(x, k, n), notice that there are two cases: whether f(n-1) in the sum or not.
- If f(n-1) is not in the sum, then x is formed as a sum using exactly k numbers from f(0), f(1), …, f(n-2).
- If f(n-1) is in the sum, then the remaining x-f(n-1) is formed using exactly k-1 numbers from f(0), f(1), …, f(n-1). (Notice that f(n-1) is still included because duplicate numbers are allowed.).
So the recurrence relation will be:
F(x, k, n)= F(x, k, n-1)+F(x-f(n-1), k-1, n)
Base cases:
- If k=0, then there are zero numbers from the series, so the sum can only be 0. Hence, F(0, 0, n)=1.
- F(x, 0, n)=0, if x is not equals to 0.
Also, there are other cases that make F(x, k, n)=0, like the following:
- If k>0 and x=0 because having at least one positive number must result in a positive sum.
- If k>0 and n=0 because there’s no possible choice of numbers left.
- If x<0 because there’s no way to form a negative sum using a finite number of nonnegative numbers.
Below is the implementation of above approach:
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; // to store fibonacci numbers // 42 second number in fibonacci series // largest possible integer int fib[43] = { 0 }; // Function to generate fibonacci series void fibonacci() { fib[0] = 1; fib[1] = 2; for ( int i = 2; i < 43; i++) fib[i] = fib[i - 1] + fib[i - 2]; } // Recursive function to return the // number of ways int rec( int x, int y, int last) { // base condition if (y == 0) { if (x == 0) return 1; return 0; } int sum = 0; // for recursive function call for ( int i = last; i >= 0 and ( float )fib[i] * ( float )y >= ( float )x; i--) { if (fib[i] > x) continue ; sum += rec(x - fib[i], y - 1, i); } return sum; } // Driver code int main() { fibonacci(); int n = 13, k = 3; cout << "Possible ways are: " << rec(n, k, 42); return 0; } |
C
// C implementation of above approach #include <stdio.h> // to store fibonacci numbers // 42 second number in fibonacci series // largest possible integer int fib[43] = { 0 }; // Function to generate fibonacci series void fibonacci() { fib[0] = 1; fib[1] = 2; for ( int i = 2; i < 43; i++) fib[i] = fib[i - 1] + fib[i - 2]; } // Recursive function to return the // number of ways int rec( int x, int y, int last) { // base condition if (y == 0) { if (x == 0) return 1; return 0; } int sum = 0; // for recursive function call for ( int i = last; i >= 0 && ( float )fib[i] * ( float )y >= ( float )x; i--) { if (fib[i] > x) continue ; sum += rec(x - fib[i], y - 1, i); } return sum; } // Driver code int main() { fibonacci(); int n = 13, k = 3; printf ( "Possible ways are: %d" ,rec(n, k, 42)); return 0; } // This code is contributed by kothavvsaakash. |
Java
//Java implementation of above approach public class AQW { //to store fibonacci numbers //42 second number in fibonacci series //largest possible integer static int fib[] = new int [ 43 ]; //Function to generate fibonacci series static void fibonacci() { fib[ 0 ] = 1 ; fib[ 1 ] = 2 ; for ( int i = 2 ; i < 43 ; i++) fib[i] = fib[i - 1 ] + fib[i - 2 ]; } //Recursive function to return the //number of ways static int rec( int x, int y, int last) { // base condition if (y == 0 ) { if (x == 0 ) return 1 ; return 0 ; } int sum = 0 ; // for recursive function call for ( int i = last; i >= 0 && ( float )fib[i] * ( float )y >= ( float )x; i--) { if (fib[i] > x) continue ; sum += rec(x - fib[i], y - 1 , i); } return sum; } //Driver code public static void main(String[] args) { fibonacci(); int n = 13 , k = 3 ; System.out.println( "Possible ways are: " + rec(n, k, 42 )); } } |
Python3
# Python3 implementation of the above approach # To store fibonacci numbers 42 second # number in fibonacci series largest # possible integer fib = [ 0 ] * 43 # Function to generate fibonacci # series def fibonacci(): fib[ 0 ] = 1 fib[ 1 ] = 2 for i in range ( 2 , 43 ): fib[i] = fib[i - 1 ] + fib[i - 2 ] # Recursive function to return the # number of ways def rec(x, y, last): # base condition if y = = 0 : if x = = 0 : return 1 return 0 Sum , i = 0 , last # for recursive function call while i > = 0 and fib[i] * y > = x: if fib[i] > x: i - = 1 continue Sum + = rec(x - fib[i], y - 1 , i) i - = 1 return Sum # Driver code if __name__ = = "__main__" : fibonacci() n, k = 13 , 3 print ( "Possible ways are:" , rec(n, k, 42 )) # This code is contributed # by Rituraj Jain |
C#
// C# implementation of above approach using System; class GFG { // to store fibonacci numbers // 42 second number in fibonacci series // largest possible integer static int [] fib = new int [43]; // Function to generate fibonacci series public static void fibonacci() { fib[0] = 1; fib[1] = 2; for ( int i = 2; i < 43; i++) fib[i] = fib[i - 1] + fib[i - 2]; } // Recursive function to return the // number of ways public static int rec( int x, int y, int last) { // base condition if (y == 0) { if (x == 0) return 1; return 0; } int sum = 0; // for recursive function call for ( int i = last; i >= 0 && ( float )fib[i] * ( float )y >= ( float )x; i--) { if (fib[i] > x) continue ; sum += rec(x - fib[i], y - 1, i); } return sum; } // Driver code static void Main() { for ( int i = 0; i < 43; i++) fib[i] = 0; fibonacci(); int n = 13, k = 3; Console.Write( "Possible ways are: " + rec(n, k, 42)); } //This code is contributed by DrRoot_ } |
PHP
<?php // PHP implementation of above approach // To store fibonacci numbers // 42 second number in fibonacci series // largest possible integer $fib = array_fill (0, 43, 0); // Function to generate // fibonacci series function fibonacci() { global $fib ; $fib [0] = 1; $fib [1] = 2; for ( $i = 2; $i < 43; $i ++) $fib [ $i ] = $fib [ $i - 1] + $fib [ $i - 2]; } // Recursive function to return // the number of ways function rec( $x , $y , $last ) { global $fib ; // base condition if ( $y == 0) { if ( $x == 0) return 1; return 0; } $sum = 0; // for recursive function call for ( $i = $last ; $i >= 0 and $fib [ $i ] * $y >= $x ; $i --) { if ( $fib [ $i ] > $x ) continue ; $sum += rec( $x - $fib [ $i ], $y - 1, $i ); } return $sum ; } // Driver code fibonacci(); $n = 13; $k = 3; echo "Possible ways are: " . rec( $n , $k , 42); // This code is contributed by mits ?> |
Javascript
<script> //Javascript implementation of above approach //to store fibonacci numbers //42 second number in fibonacci series //largest possible integer let fib= new Array(43); //Function to generate fibonacci series function fibonacci() { fib[0] = 1; fib[1] = 2; for (let i = 2; i < 43; i++) fib[i] = fib[i - 1] + fib[i - 2]; } //Recursive function to return the //number of ways function rec(x,y,last) { // base condition if (y == 0) { if (x == 0) return 1; return 0; } let sum = 0; // for recursive function call for (let i = last; i >= 0 && fib[i] * y >= x; i--) { if (fib[i] > x) continue ; sum += rec(x - fib[i], y - 1, i); } return sum; } //Driver code fibonacci(); let n = 13, k = 3; document.write( "Possible ways are: " + rec(n, k, 42)); // This code is contributed by rag2127 </script> |
Output:
Possible ways are: 2