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 integerint fib[43] = { 0 };// Function to generate fibonacci seriesvoid 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 codeint 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 integerint fib[43] = { 0 };// Function to generate fibonacci seriesvoid 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 codeint 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 approachpublic 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 approachusing 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 seriesfunction 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 codefibonacci();$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
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 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
