Given two numbers K and N. The task is to represent the given number K as a sum of several N-bonacci numbers.
Examples:
Input: K = 21, N = 5
Output: 3
The three numbers of the 5-bonacci numbers are: 16, 4, 1.
Explanation:
For N = 5, the series will be: 1, 1, 2, 4, 8, 16, 31, 61, 120, and so on. The three numbers 16, 4 and 1 add up to 21.Input: K = 500, N = 43
Output: 6
The numbers of 43-bonacci that add up to 500 are: 256 128 64 32 16 4
Naive Approach:
The simplest approach is to generate the N-bonacci series upto 50 terms and store their values in an array. Find the subset of the array which has the given sum and print the size of the subset.
Time Complexity: O(2N)
Efficient Approach: This approach is based on the efficient approach on how to form N-bonacci numbers, discussed in this article.
Follow the steps below to solve the problem:
- Generate the N-bonacci series and store the values in an array, say N_bonacci[]. (upto 50 terms)
- Initialize another array, ans[], for saving the numbers from the series whose sum is K.
- Traverse the N-bonacci array in the reverse order and keep checking if, K – N_bonacci[i] >= 0. If true, then push the N_bonacci[i] to the ans array, and reduce K to K – N_bonacci[i].
- Continue decrementing K till it becomes 0, and then finally output the size and the elements of ans array.
Below is the implementation of the above approach:
C++
// C++ program for the above problem #include <bits/stdc++.h> using namespace std; // array to store the N-Bonacci series long long N_bonacci[100]; // Function to express K as sum of // several N_bonacci numbers void N_bonacci_nums(int n, int k) { N_bonacci[0] = 1; for (int i = 1; i <= 50; ++i) { for (int j = i - 1; j >= i - k and j >= 0; --j) N_bonacci[i] += N_bonacci[j]; } vector<long long> ans; for (int i = 50; i >= 0; --i) if (n - N_bonacci[i] >= 0) { ans.push_back(N_bonacci[i]); n -= N_bonacci[i]; } if (ans.size() == 1) ans.push_back(0); cout << ans.size() << endl; for (int i = 0; i < ans.size(); ++i) cout << ans[i] << ", "; } // Driver code int main() { int n = 21, k = 5; N_bonacci_nums(n, k); return 0; } |
Java
// Java program for the above problem import java.util.*; class GFG{ // Array to store the N-Bonacci series public static long []N_bonacci= new long [100]; // Function to express K as sum of // several N_bonacci numbers @SuppressWarnings("unchecked") public static void N_bonacci_nums(int n, int k) { N_bonacci[0] = 1; for(int i = 1; i <= 50; ++i) { for(int j = i - 1; j >= i - k && j >= 0 ;--j) N_bonacci[i]+= N_bonacci[j]; } Vector ans = new Vector(); for(int i = 50; i >= 0; --i) if (n - N_bonacci[i] >= 0) { ans.add(N_bonacci[i]); n -= N_bonacci[i]; } if (ans.size() == 1) ans.add(0); System.out.println(ans.size()); for(int i = 0; i < ans.size(); ++i) System.out.print(ans.get(i) + ", "); } // Driver code public static void main(String args[]) { int n = 21, k = 5; N_bonacci_nums(n, k); } } // This code is contributed by SoumikMondal |
Python3
# Python3 program for the above problem # Array to store the N-Bonacci series N_bonacci = [0] * 100# Function to express K as sum of # several N_bonacci numbers def N_bonacci_nums(n, k): N_bonacci[0] = 1 for i in range(1, 51): j = i - 1 while j >= i - k and j >= 0: N_bonacci[i] += N_bonacci[j] j -= 1 ans = [] for i in range(50, -1, -1): if (n - N_bonacci[i] >= 0): ans.append(N_bonacci[i]) n -= N_bonacci[i] if (len(ans) == 1): ans.append(0) print(len(ans)) for i in ans: print(i, end = ", ") # Driver code if __name__ == '__main__': n = 21 k = 5 N_bonacci_nums(n, k) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above problem using System;using System.Collections.Generic; class GFG{// Array to store the N-Bonacci series public static long []N_bonacci = new long [100]; // Function to express K as sum of // several N_bonacci numbers static void N_bonacci_nums(long n, long k) { N_bonacci[0] = 1; for(int i = 1; i <= 50; ++i) { for(int j = i - 1; j >= i - k && j >= 0; --j) N_bonacci[i] += N_bonacci[j]; } List<long> ans = new List<long>(); for(int i = 50; i >= 0; --i) if (n - N_bonacci[i] >= 0) { ans.Add(N_bonacci[i]); n -= N_bonacci[i]; } if (ans.Count == 1) ans.Add(0); Console.WriteLine(ans.Count); for(int i = 0; i < ans.Count; ++i) Console.Write(ans[i] + ", ");} // Driver codestatic void Main(){ long n = 21, k = 5; N_bonacci_nums(n, k); }}// This code is contributed by divyeshrabadiya07 |
Javascript
<script>// Javascript program for the above problem // Array to store the N-Bonacci series let N_bonacci= new Array(100);for(let i = 0; i < 100; i++){ N_bonacci[i] = 0;}// Function to express K as sum of // several N_bonacci numbers function N_bonacci_nums(n, k){ N_bonacci[0] = 1; for(let i = 1; i <= 50; ++i) { for(let j = i - 1; j >= i - k && j >= 0 ;--j) N_bonacci[i]+= N_bonacci[j]; } let ans = []; for(let i = 50; i >= 0; --i) if (n - N_bonacci[i] >= 0) { ans.push(N_bonacci[i]); n -= N_bonacci[i]; } if (ans.length == 1) ans.push(0); document.write(ans.length+"<br>"); for(let i = 0; i < ans.length; ++i) document.write(ans[i] + ", "); }// Driver code let n = 21, k = 5; N_bonacci_nums(n, k); // This code is contributed by unknown2108</script> |
Output:
3 16, 4, 1,
Time Complexity: O(K * K)
Auxiliary Space: O(1)
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!
